# I tried implementing a simple pathfinding algorithm by following along with wikipedia

So not really sure how to phrase this. It’s not really a specific question as such just more like: “Hey look at this, where is it obviously pants?”

So with all the free time recently I thought I’d try to make a tower defence type game. First off I generate a map by simulating a “snake” moving randomly right, up and down until he reaches the end and making a “maze” out of the result. Seems to work ok, however not the main thrust of my question.

I’ve tried to implement pathfinding through the resulting maze, struggled to find anything I could simply “drop into” processing so in the end I’ve tried to implement the pseudocode (well not even that really just a logical description) in the wikipedia article on the subject. Just going step by step and trying to recreate it as best I know how.

Anyhoo, it kinda works, like 95% of the time. I must stress what I’m not looking for here is for someone to magically come along and debug my code for me, just more like, general advice. Like “Why on earth are you doing that to do that, just use this” kinda pointers. just feels really messy and inelegant and spaghettified.

This the meat of the pathfinding code:

``````//////////////////////////////////////////////////////// Beginning Mapping environment for pathfinding
class PathFindCoord {
int posX, posY, distanceCounter;
PathFindCoord(int pX, int pY, int dCounter) {
posX = pX;
posY = pY;
distanceCounter = dCounter;
}
}

int testEndofQueue;
ArrayList<PathFindCoord> pathFindCoords = new ArrayList<PathFindCoord>();
ArrayList<PathFindCoord> pathFindCoordsTestingList = new ArrayList<PathFindCoord>();
ArrayList<PathFindCoord> BestPathFindCoords = new ArrayList<PathFindCoord>();
void addToPathFindArrayList(int posX, int posY, int distanceCounter) {
}
void addToPathFindArrayTestingList(int posX, int posY, int distanceCounter) {
}
void addToBestPath(int posX, int posY, int distanceCounter) {
}

void pathFind() {
boolean pathFound = false;
int maxIter = 0;
while (pathFound == false) {
for (int i = pathFindCoords.size() - 1; i >= 0; i--) {
PathFindCoord part = pathFindCoords.get(i);
//get left cell and put into testing arraylist
if (part.posX - 1 >= 0) { //check we're not off the grid
addToPathFindArrayTestingList(part.posX - 1, part.posY, part.distanceCounter + 1);
}
//get right cell and put into testing arraylist
if (part.posX + 1 < 24) { //check we're not off the grid
addToPathFindArrayTestingList(part.posX + 1, part.posY, part.distanceCounter + 1);
}
//get top cell and put into testing arraylist
if (part.posY - 1 >= 0) { //check we're not off the grid
addToPathFindArrayTestingList(part.posX, part.posY - 1, part.distanceCounter + 1);
}
//get bottom cell and put into testing arraylist
if (part.posY + 1 < 12) { //check we're not off the grid
addToPathFindArrayTestingList(part.posX, part.posY + 1, part.distanceCounter + 1);
}
//Now perform checks on the testing arraylist
for (int x = pathFindCoordsTestingList.size() - 1; x >= 0; x--) { //Check for walls, Look up in wallPath array
PathFindCoord partWall = pathFindCoordsTestingList.get(x);
try {
if (wallPath[partWall.posX][partWall.posY] == 0) {
pathFindCoordsTestingList.remove(x);
}
}
catch (ArrayIndexOutOfBoundsException e) {
e.printStackTrace();
}
}
for (int g = pathFindCoordsTestingList.size() - 1; g >= 0; g--) { //Check for distance and similarity
PathFindCoord partDistance = pathFindCoordsTestingList.get(g);
for (int j = pathFindCoords.size() - 1; j >= 0; j--) {
PathFindCoord partCompare = pathFindCoords.get(j);
try {
if (partDistance.posX == partCompare.posX && partDistance.posY == partCompare.posY && partDistance.distanceCounter >= partCompare.distanceCounter) {
pathFindCoordsTestingList.remove(g);
break;
}
}
catch (ArrayIndexOutOfBoundsException e) {
e.printStackTrace();
}
}
}
//Add suitable candidates to main queue
for (int y = pathFindCoordsTestingList.size() - 1; y >= 0; y--) {
}
}
pathFindCoordsTestingList.clear(); // Clear testing list
//Have we reached the start point
testEndofQueue = pathFindCoords.size() -1;
PathFindCoord partTestComplete = pathFindCoords.get(testEndofQueue);
int testXpos = partTestComplete.posX;
int testYpos = partTestComplete.posY;
if ((testXpos == 0  && testYpos == startPos) || maxIter >= 50) {
pathFound = true;
}
}

//////////////////////////////////////////////////// Determine Best Path

PathFindCoord BestPathNode = pathFindCoords.get(testEndofQueue);
int lowestDistanceValue = BestPathNode.distanceCounter;
int compareDistanceValue = 0;
int indexOfLowestDistanceValue = 0;
for (int k = 60; k >= 0; k--) {
lowestDistanceValue = BestPathNode.distanceCounter;
for (int j = pathFindCoords.size() - 1; j >= 0; j--) { // Find adjacent nodes
PathFindCoord partCompare = pathFindCoords.get(j);

if (partCompare.posX == (BestPathNode.posX + 1) && partCompare.posY == BestPathNode.posY
|| partCompare.posX == (BestPathNode.posX - 1) && partCompare.posY == BestPathNode.posY
||  partCompare.posY == (BestPathNode.posY + 1) && partCompare.posX == BestPathNode.posX
|| partCompare.posY == (BestPathNode.posY - 1) && partCompare.posX == BestPathNode.posX ) {

}
}

for (int v = pathFindCoordsTestingList.size() - 1; v >= 0; v--) { // Find lowest distance value

PathFindCoord partCompare = pathFindCoordsTestingList.get(v);
compareDistanceValue = partCompare.distanceCounter;

if (compareDistanceValue < lowestDistanceValue) {

lowestDistanceValue = compareDistanceValue;
indexOfLowestDistanceValue = v;
}
}

pathFindCoordsTestingList.clear();

break;
}
}
}
``````

if you want the whole thing to run it I’m happy to provide.

Anyway, yeah, thanks.

1 Like

There is the Path Finder library and the AI for 2D Games library which includes path finding but is more complicated.

1 Like

Thanks for sharing this!

When you say 95%, what kind of errors do you encounter?