Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (538)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (600)
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 1605 times)
0 Members and 1 Guest are viewing this topic.
Offline MBrenaman

Junior Devvie




Javanaut


« 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: 56
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).

[ TriangularPixels.com - 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
http://gamedev.net/reference/list.asp?categoryid=18#94
http://gamedev.net/reference/list.asp?categoryid=44
(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




Javanaut


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

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

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (29 views)
2014-12-15 09:26:44

Mr.CodeIt (20 views)
2014-12-14 19:50:38

BurntPizza (40 views)
2014-12-09 22:41:13

BurntPizza (75 views)
2014-12-08 04:46:31

JscottyBieshaar (37 views)
2014-12-05 12:39:02

SHC (50 views)
2014-12-03 16:27:13

CopyableCougar4 (47 views)
2014-11-29 21:32:03

toopeicgaming1999 (113 views)
2014-11-26 15:22:04

toopeicgaming1999 (100 views)
2014-11-26 15:20:36

toopeicgaming1999 (30 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
java-gaming.org 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‑gaming.org
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!