Created
December 20, 2015 16:51
-
-
Save tim-peters/6487590f58d308c62def to your computer and use it in GitHub Desktop.
A very simple path finding algorythm in processing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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