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) {
pathFindCoords.add(new PathFindCoord(posX, posY, distanceCounter));
}
void addToPathFindArrayTestingList(int posX, int posY, int distanceCounter) {
pathFindCoordsTestingList.add(new PathFindCoord(posX, posY, distanceCounter));
}
void addToBestPath(int posX, int posY, int distanceCounter) {
BestPathFindCoords.add(new PathFindCoord(posX, posY, distanceCounter));
}
void pathFind() {
boolean pathFound = false;
int maxIter = 0;
addToPathFindArrayList(tRX, tRY, 0); //Add initial target tile to start of queue
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--) {
PathFindCoord partAdd = pathFindCoordsTestingList.get(y);
addToPathFindArrayList(partAdd.posX, partAdd.posY, partAdd.distanceCounter);
}
}
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);
addToBestPath(BestPathNode.posX, BestPathNode.posY, BestPathNode.distanceCounter);
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 ) {
addToPathFindArrayTestingList(partCompare.posX, partCompare.posY, partCompare.distanceCounter);
}
}
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;
}
}
PathFindCoord BestPathNodetoAdd = pathFindCoordsTestingList.get(indexOfLowestDistanceValue);
addToBestPath(BestPathNodetoAdd.posX, BestPathNodetoAdd.posY, BestPathNodetoAdd.distanceCounter);
BestPathNode.posX = BestPathNodetoAdd.posX;
BestPathNode.posY = BestPathNodetoAdd.posY;
BestPathNode.distanceCounter = BestPathNodetoAdd.distanceCounter;
pathFindCoordsTestingList.clear();
if (BestPathNodetoAdd.distanceCounter == 0) {
break;
}
}
}
if you want the whole thing to run it I’m happy to provide.
Anyway, yeah, thanks.