Skip to content

Instantly share code, notes, and snippets.

@tim-peters
Created December 20, 2015 16:51
Show Gist options
  • Save tim-peters/6487590f58d308c62def to your computer and use it in GitHub Desktop.
Save tim-peters/6487590f58d308c62def to your computer and use it in GitHub Desktop.
A very simple path finding algorythm in processing
/*
* Processing 2.0 File
* Author: Tim J. Peters <tim-peters>
* Released under CC BY 3.0
*/
int dotSize = 100; // scale
int gridSize = 10; // size of the map (grid)
int[] waysToKnot;
IntList starts = new IntList(),
ends = new IntList(),
pathFound;
queuedEachWayFrom[] queue = new queuedEachWayFrom[99999];
int filler = 0, reader = 0;
class queuedEachWayFrom {
int start, goal;
IntList passedStartIDs;
queuedEachWayFrom(int _start, int _goal, IntList _passedStartIDs) {
start = _start; goal = _goal; passedStartIDs = _passedStartIDs; }
public void run() {
eachWayFrom(start, goal, passedStartIDs); }
}
void setup() {
textSize(20);
size((1+gridSize)*dotSize,(1+gridSize)*dotSize);
translate(dotSize,dotSize);
/* Just preparation work (I was too lazy to create the vector map on my own */
// draw points grid and define possible ways
for(int x = 0;x<gridSize;x++)
for(int y = 0;y<gridSize;y++) {
int id = x*gridSize+y;
text(id,x*dotSize,y*dotSize);
ellipse(x*dotSize,y*dotSize,1,1);
//way up
if(y>0)
addWay(id, id-1);
//way down
if(y<gridSize-1)
addWay(id,id+1);
//way right
if(x<gridSize-1)
addWay(id,id+gridSize);
//way left
if(x>0)
addWay(id,id-gridSize);
}
pathFound = new IntList(); waysToKnot = new int[starts.size()]; // path finding variables
eachWayFrom(11,88,new IntList()); // FIND WAY FROM POINT 11 to POINT 88 ++++++++++++++++
while(queue[reader] != null)
queue[reader++].run();
for (int n=1; n<pathFound.size(); n++) {
debugWay(pathFound.get(n-1),pathFound.get(n));
}
}
void eachWayFrom(int start, int goal, IntList passedStartIDs) {
passedStartIDs.append (start); // add current step (increases cost by one)
if (start == goal) { // if destination is reached
if(pathFound.size() == 0 || passedStartIDs.size() < pathFound.size()) // check whether it's the best way found yet
pathFound = passedStartIDs;
} else {
if ((waysToKnot[start] == 0 || waysToKnot[start] > passedStartIDs.size()) && (pathFound.size() == 0 || pathFound.size() > passedStartIDs.size())) { // if this point was *not* already checked or just checked with more steps
waysToKnot[start] = passedStartIDs.size(); // set this way as the best so far
IntList wayAwayIDs = allIndexOf (start, starts); // all startIDs that start at ends[endID]
for (int n=0; n<wayAwayIDs.size(); n++) // for each track away from this point...
if(passedStartIDs.size() <= 1 || (passedStartIDs.size() > 1 && ends.get(wayAwayIDs.get(n)) != passedStartIDs.get(passedStartIDs.size()-2)))
queue[filler++] = new queuedEachWayFrom (ends.get(wayAwayIDs.get(n)), goal, new IntList(passedStartIDs)); // increase queue by the ways to check
}
}
}
void addWay(int from, int to) { // adds from to starts and to to ends
starts.append(from);
ends.append(to);
}
// helper function: Dunno if this is implemented in processing 2.0 so I re-implemented it quickly (is standard in almost every language)
IntList allIndexOf(int content, IntList list) {
IntList results = new IntList();
for(int n=0;n<list.size();n++)
if(list.get(n) == content)
results.append(n);
return results;
}
/* Graphical helper functions */
int[] getPositionFromId(int id) {
int x = floor((float)id/gridSize);
int y = id % gridSize;
int[] result = {x,y};
return result;
}
// draws an arrow between points with ids from and to
void debugWay(int from, int to) {
int[] p1 = getPositionFromId(from);
int[] p2 = getPositionFromId(to);
arrow(p1[0]*dotSize,p1[1]*dotSize,p2[0]*dotSize,p2[1]*dotSize);
}
// draws an arrow from x to y
void arrow(int x1, int y1, int x2, int y2) {
line(x1, y1, x2, y2);
pushMatrix();
translate(x2, y2);
float a = atan2(x1-x2, y2-y1);
rotate(a);
line(0, 0, -10, -10);
line(0, 0, 10, -10);
popMatrix();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment