Ok, I tried making it A* again. It runs great, except, I every now and then I get trapped in an infinite loop and I run out of memory. Also, things get slow when I leave one big room with lots enemies to go to another room with lots of enemies but not when I enter a room with lots of enemies from a room with very little…
Anyways, here’s my code so far. Please bear in mind that these are my first attempts at real pathfinding and I’ve been using Java only since May of this year. So I don’t know what I might be doing wrong.
EDIT: also, I recalculate the neighbors beacuse some enemies can walk through some terrian and some can’t.
//
//Constructs a list of pathNodes from npc to dx,dy
//
private List getPath(Npc npc,int dx,int dy){
if( (isBlocked(dungeonMap[currFloor][dx-1][dy-1],npc) || npcGrid[currFloor][dx-1][dy-1]!=0) &&
(isBlocked(dungeonMap[currFloor][dx][dy-1],npc) || npcGrid[currFloor][dx][dy-1]!=0) &&
(isBlocked(dungeonMap[currFloor][dx+1][dy-1],npc) || npcGrid[currFloor][dx+1][dy-1]!=0) &&
(isBlocked(dungeonMap[currFloor][dx-1][dy],npc) || npcGrid[currFloor][dx-1][dy]!=0) &&
(isBlocked(dungeonMap[currFloor][dx+1][dy],npc) || npcGrid[currFloor][dx+1][dy]!=0) &&
(isBlocked(dungeonMap[currFloor][dx-1][dy+1],npc) || npcGrid[currFloor][dx-1][dy+1]!=0) &&
(isBlocked(dungeonMap[currFloor][dx][dy+1],npc) || npcGrid[currFloor][dx][dy+1]!=0) &&
(isBlocked(dungeonMap[currFloor][dx+1][dy+1],npc) || npcGrid[currFloor][dx+1][dy+1]!=0)
){
return null;
}
PathNode startNode = pathNodes[npc.getX()][npc.getY()];
PathNode goalNode = pathNodes[dx][dy];
// list of visited nodes
LinkedList closedList = new LinkedList();
// list of nodes to visit (sorted)
LinkedList openList = new LinkedList();
openList.add(startNode);
startNode.pathParent = null;
while (!openList.isEmpty()) {
PathNode node = (PathNode)openList.removeFirst();
if (node.x == goalNode.x && node.y == goalNode.y) {
//path found!
return constructPath(node);
}
node.neighbors.clear();
// add neighbors to the open list
for(int yv=-1;yv<=1;yv+=1){
for(int xv=-1;xv<=1;xv+=1){
if(!(xv==0 && yv==0)){
if(node.x+xv>=0 && node.y+yv>=0 && node.x+xv<MAP_WIDTH && node.y+yv<MAP_HEIGHT){
if(!isBlocked(dungeonMap[currFloor][node.x+xv][node.y+yv],npc) && npcGrid[currFloor][node.x+xv][node.y+yv]==0){
node.neighbors.add(pathNodes[node.x+xv][node.y+yv]);
}
}
}
}
}
for(int count=0;count<node.neighbors.size();count++){
PathNode neighborNode = (PathNode)node.neighbors.get(count);
boolean isOpen = openList.contains(neighborNode);
boolean isClosed = closedList.contains(neighborNode);
int costFromStart=distance(node.x,node.y,npc.getX(),npc.getY())+1;
//Check if the neighbor has not been traversed or if a shorter path to this neighboor is found
if((!isOpen && !isClosed) || costFromStart<distance(neighborNode.x,neighborNode.y,npc.getX(),npc.getY())){
neighborNode.pathParent=node;
if(isClosed){
closedList.remove(neighborNode);
}
if(!isOpen){
boolean wasAdded=false;
for(int addCount=0;addCount<openList.size();addCount++){
PathNode testNode = (PathNode)openList.get(addCount);
if(distance(dx,dy,neighborNode.x,neighborNode.y)<=distance(dx,dy,testNode.x,testNode.y)){
openList.add(addCount,neighborNode);
wasAdded=true;
break;
}
}
if(!wasAdded)
openList.addLast(neighborNode);
}
}
}
closedList.add(node);
}
// no path found
return null;
}
private List constructPath(PathNode node) {
LinkedList path = new LinkedList();
while (node.pathParent != null) {
path.addFirst(pathNodes[node.x][node.y]);
node = node.pathParent;
}
return path;
}
Pathnodes simple contain x,y List neighbors and reference to its parent. I made an array of pathnodes to cover one floor so I don’t have to create any new objects… except for when I contruct a path.
I’ll check out those links right now that you left abies.
In such case manhattan metric could be used - probably good enough and a lot faster.