Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (727)
Games in Android Showcase (217)
games submitted by our members
Games in WIP (796)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Faster Pathfinding...  (Read 2560 times)
0 Members and 1 Guest are viewing this topic.
Offline MBrenaman

Junior Devvie


« Posted 2004-07-25 15:05:39 »

Ok, well, right now I'm making a tile based dungeon crawl and my pathfinding is slow, even for a turn-based game. Right now I'm using Breadth-First-Search beacuse I tried A*, and it seemed slower...

I was wondering if anyone could hook me up with a fast pathfinding algorithm for finding the shortest open path on a tile grid from one point to the other.

Not much of what I found was in Java or tile grid specific.

Any help would be grealty appreciated. If you want to see how I'm doing my BFS search, I'll post the code. Maybe my way is just to darn slow.  :-/

-Mathew Brenaman
Offline Orangy Tang

JGO Kernel

Medals: 57
Projects: 11

Monkey for a head

« Reply #1 - Posted 2004-07-25 15:21:46 »

Er, unless I'm horribly mistaken, but A* cannot possibly be slower than a breadth-first search. BF is the slowest way possible, and A* only degenerates into a straight BF with a bad heristic function.

I'd suggest having another look at A*. Perhaps your heristic function is bad or wrong, or you've made a mistake in your implementation (like not managing your open and closed lists properly).

[ - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline abies

Senior Devvie

« Reply #2 - Posted 2004-07-25 19:18:01 »

For totally wrong heuristic (which gives opposite results from real ones) it should be worse. But even for reasonable heuristic (but non-perfect) it can be slower because of the cost of heuristic function itself.

For example, if you use euclidean distance between points as heuristic function, square root can take more time than traversing few nodes blindly without it Smiley In such case manhattan metric could be used - probably good enough and a lot faster.

You probably already know it but take a look at
(second link especially for line of sight algorithms).

And post your code here, maybe we will discover something simple which can improve the situation. I remember that I have done screen-coord-to-hex-coord algorithm once and it got 3 times faster when I have used (int)floatVariable instead of Math.floor(floatVariable) everywhere (I could do this because floatVariable was >0).

Artur Biesiadowski
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline MBrenaman

Junior Devvie


« Reply #3 - Posted 2004-07-26 04:21:48 »

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();
   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);

       // 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){

       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())){

             boolean wasAdded=false;

             for(int addCount=0;addCount<openList.size();addCount++){
               PathNode testNode = (PathNode)openList.get(addCount);





   // no path found
   return null;

 private List constructPath(PathNode node) {
   LinkedList path = new LinkedList();
   while (node.pathParent != null) {
     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.

-Mathew Brenaman
Pages: [1]
  ignore  |  Print  
You cannot reply to this message, because it is very, very old.

Archive (299 views)
2017-04-27 17:45:51

buddyBro (486 views)
2017-04-05 03:38:00

CopyableCougar4 (933 views)
2017-03-24 15:39:42

theagentd (946 views)
2017-03-24 15:32:08

Rule (955 views)
2017-03-19 12:43:22

Rule (924 views)
2017-03-19 12:42:17

Rule (925 views)
2017-03-19 12:36:21

theagentd (988 views)
2017-03-16 05:07:07

theagentd (903 views)
2017-03-15 22:37:06

theagentd (696 views)
2017-03-15 22:32:18
List of Learning Resources
by elect
2017-03-13 14:05:44

List of Learning Resources
by elect
2017-03-13 14:04:45

SF/X Libraries
by philfrei
2017-03-02 08:45:19

SF/X Libraries
by philfrei
2017-03-02 08:44:05

SF/X Libraries
by SkyAphid
2017-03-02 06:38:56

SF/X Libraries
by SkyAphid
2017-03-02 06:38:32

SF/X Libraries
by SkyAphid
2017-03-02 06:38:05

SF/X Libraries
by SkyAphid
2017-03-02 06:37:51 is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!