Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (481)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (547)
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  
  Pathfinding efficiency  (Read 2583 times)
0 Members and 1 Guest are viewing this topic.
Offline Gibbo3771
« Posted 2014-03-18 10:08:30 »

I have implemented an A* algorithm into my game and I am having a few issues with it.

At first I was using calculate method that would take the start position and end position, which would jump into a while loop while searching, locking up my game for about 5-6 seconds. I then split it into 2 methods, one that sets the start and end positions, sets up the open and closed list. Then an update method that runs in the entity update method that only runs when a boolean is set, such as

1  
boolean needsPath;


This works about 75% of the time, other times it completely deadlocks my game and crashes it, however when I press the key to initialize the pathfinder and move my entity, it takes about 5 seconds to actually move.

It is exactly 47 tiles to my destination, this means it checks 188 nodes as it checks in 4 compass directions, N, E, W, S.

Here is my pathfinder:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
   public Path calculatePath(int startX, int startY, int destX, int destY) {

      map.setStart(startX, startY);
      map.setDestination(destX, destY);

      /* Check if the destination is passable, if not, just return null */
      if (!(map.getNode(destX, destY)).isPassable) {
         return null;
      }

      /* Set the distance from start at 0, we have not moved yet */
      map.getStartNode().setDistanceFromStart(0);
      /*
       * We need to clear our arrays before calculating a new path, if we
       * don't it will be all f**ked up
       */

      open.clear();
      closed.clear();
      /* Add our start node to the open list */
      open.add(map.getStartNode());

      /*
       * Basically while our open array has objects, we obviously have not
       * found our path to destination yet
       */

      while (open.size != 0) {
         /* Get the first node in our open list */
         Node current = open.first();

         /*
          * If the current node position is the same as the dest position, we
          * must be done calculating the path
          */

         if ((current.getPosition().x == map.getDestPos().x)
               && (current.getPosition().y == map.getDestPos().y)) {
            return recreate(current);
         }

         /*
          * Remove the current node from the open list, it has already been
          * searched
          */

         open.removeValue(current, true);
         /* Add it to the closed list */
         closed.add(current);

         for (Node neighbour : current.getNeighbours()) {
            boolean neighbourShorter;

            /*
             * If this node is in the closed list we have already searched
             * it, move on
             */

            if (closed.contains(neighbour, true))
               continue;



            /*
             * If the node is not passable, E.g a wall, just move on and
             * keep looking
             */

            if (!neighbour.isPassable) {
               continue;
            } else {

               /* calculate the neighbours distance from the start point */
               float neighbourDistanceFromStart = (current
                     .getDistanceFromStart() + map.compareNodeDistance(
                     current, neighbour));

               /* Add our neighbour to the open list if not already there */
               if (!open.contains(neighbour, true)) {
                  open.add(neighbour);
                  open.sort();
                  neighbourShorter = true;

                  /*
                   * if the neighbour is closer to the start, path is
                   * still shorter
                   */

               } else if (neighbourDistanceFromStart < current
                     .getDistanceFromStart()) {
                  neighbourShorter = true;
               } else {
                  neighbourShorter = false;
               }

               /* If the neighour is the shortest path, use that node */
               if (neighbourShorter) {
                  /*
                   * Set the neighbours previous node to the one we are
                   * currently on
                   */

                  neighbour.setPreviousNode(current);
                  neighbour
                        .setDistanceFromStart(neighbour.distanceFromStart);
                  neighbour.setHeuristicalDistanceToDest(heuristic
                        .getEstimatedDistanceToDest(
                              (int) neighbour.getPosition().x,
                              (int) neighbour.getPosition().y,
                              (int) map.getDestPos().x,
                              (int) map.getDestPos().y));
               }

            }
         }

      }

      return null;

   }


It uses an exact heuristical method, as in tiles do not have move values as such. Instead it calculates the distance from the current  node to the end node using a straight line, this is shitty atm and seems to result in my pathfinder "hugging" walls at points in the journey. Any idea how I can improve this? Should I just move over to the manhatten method and give nodes hardcoded values, this should simplify the math.

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
Offline Thats Great
« Reply #1 - Posted 2014-03-18 10:21:33 »

Your pathfinding runs on the game thread?

I think that is generally a bad idea. You should instead use a separated Thread.

Take a look at Future and Callables.
Offline princec

JGO Kernel


Medals: 362
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #2 - Posted 2014-03-18 10:34:04 »

My pathfinding (until recently) ran in the game thread and by and large it's fine to do so because of the design of the A* algorithm. A* is designed to be run step-wise. You can run as many steps as you see fit every frame. You only begin movement when A* tells you that it succeeded or failed to find its goal.

Try at first with 1 step per frame update. That way you'll be waiting approx 3 seconds before movement begins at 60Hz. Increase until you're happy with the performance and movement delay balance.

When that's working, have a think about optimising your open and closed lists, and the heuristic used for searching.

Cas Smiley

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Gibbo3771
« Reply #3 - Posted 2014-03-18 11:01:51 »

Your pathfinding runs on the game thread?

I think that is generally a bad idea. You should instead use a separated Thread.

Take a look at Future and Callables.

I will if I can at least get it to work properly, currently as it stands it should not crash my game, lock it up yes, crash no.

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
Offline Gibbo3771
« Reply #4 - Posted 2014-03-18 13:09:15 »

My pathfinding (until recently) ran in the game thread and by and large it's fine to do so because of the design of the A* algorithm. A* is designed to be run step-wise. You can run as many steps as you see fit every frame. You only begin movement when A* tells you that it succeeded or failed to find its goal.

Try at first with 1 step per frame update. That way you'll be waiting approx 3 seconds before movement begins at 60Hz. Increase until you're happy with the performance and movement delay balance.

When that's working, have a think about optimising your open and closed lists, and the heuristic used for searching.

Cas Smiley

Thanks for your advice Cas, I will probably later introduce multi-threading for the pathfinding and use a step based search, rather than "fry the cpu and do it asap" approach, for now I just really want to get this working.

So far I can get the entity to go anywhere I want, quickly, it moves instantly regardless of map size (tested 128x128). However the problem seems to be when I want to move again.

Say I click somewhere, my entity moves there easily enough, dodging everyhting in it's path. When reaching my destination I reset everything by simply nullifying the path object. Then if I click somewhere else it should create a new path using the above algorithm but instead it just locks up and crashes my game.

What could possibly be going wrong second time around? Any ideas? Do not see any abnormal memory increase.

Could this be due to me not controlling how quickly the algorithm searches like you suggested?

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
Offline Damocles
« Reply #5 - Posted 2014-03-18 13:19:04 »

Try "nullifying the path object" before the first path-search,

If it crashed there already, its not related to the path-search itself, but your reset approach.

Offline princec

JGO Kernel


Medals: 362
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #6 - Posted 2014-03-18 13:30:20 »

What could possibly be going wrong second time around? Any ideas? Do not see any abnormal memory increase.

Could this be due to me not controlling how quickly the algorithm searches like you suggested?
Dude, you must learn to use the debugger.

When the game hangs, go into Eclipse (presumably) and pause the application. You'll see exactly where you are then.

Cas Smiley

Offline Gibbo3771
« Reply #7 - Posted 2014-03-18 14:01:49 »

What could possibly be going wrong second time around? Any ideas? Do not see any abnormal memory increase.

Could this be due to me not controlling how quickly the algorithm searches like you suggested?
Dude, you must learn to use the debugger.

God damn, I go through stages of using and I am like "this is awsome", then I forget it exists!

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
Offline Gibbo3771
« Reply #8 - Posted 2014-03-18 14:32:01 »

Try "nullifying the path object" before the first path-search,

If it crashed there already, its not related to the path-search itself, but your reset approach.

Hm nope, it must have something to do with my entity movement.

If I disable movement, I can click and go mental everywhere and show me the path to such a location. It's one of those bugs, the ones that don't tell why it is breaking, it just breaks lol.

I am going to completely rewrite my move method, here is how it has atm:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
/**
    * Update this enemy and keep the health, weapons and what not in check
    */

   public void update() {

      /* Check if we have a path before we decide to move this entity */
      if (hasPath()) {
         if (moveToDest()) {
            body.applyLinearImpulse(speed * MathUtils.cos(angle), speed
                  * MathUtils.sin(angle), 0, 0, true);
            body.setTransform(body.getPosition(), angle);
         }
      } else {
         // TODO Later we do other stuff
        if (Gdx.input.isKeyPressed(Keys.RIGHT)) {
            velocity.set(0.05f, 0);
         } else if (Gdx.input.isKeyPressed(Keys.LEFT)) {
            velocity.set(-0.05f, 0);
         } else if (Gdx.input.isKeyPressed(Keys.UP)) {
            velocity.set(0, -0.05f);
         } else if (Gdx.input.isKeyPressed(Keys.DOWN)) {
            velocity.set(0, 0.05f);
         } else {
            velocity.set(0, 0);
         }


      }
      body.applyLinearImpulse(velocity.x, velocity.y, 0, 0, true);
   }


The move to dest method :

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
/**
    * Move this enemy to a destination given by the pathfinder
    */

   public boolean moveToDest() {

      node = path.getWaypoint(nextNode);
      angle = MathUtils.atan2(node.getPosition().y - body.getPosition().y,
            node.getPosition().x - body.getPosition().x);
      if (node.getPosition().dst(body.getPosition()) < 0.5f) {
         if (nextNode < path.waypoints.size - 1)
            nextNode++;
      }
      if (body.getPosition().dst(path.getLastWaypoint().getPosition()) < 0.1f) {
         // this.path = null;
        nextNode = 0;
         return false;
      }
      return true;
   }


I think there might be some hidden recursion there I ain't see, I am going to not use that stupid boolean method.

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
Offline Gibbo3771
« Reply #9 - Posted 2014-03-20 12:14:38 »

I seem to have narrowed the error down.

It seems to happen with my NodeMap, this is the class that holds all the available nodes in a 2D array that matches with my tiles.

If I wipe this array and re-create it, it seems to stop it from crashing but I have no idea why, it's not as if the array is modified in anyway, it is only passed as reference.

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Gibbo3771
« Reply #10 - Posted 2014-03-20 17:15:56 »

I AM JESUS.

Thank f**king god seriously, this has been driving me nuts for 3 days. I found the problem.

The way you create the waypoints is start at the end and work your way back, adding each node to the array and then sort by distance. Basically every Node has a field called previous node, like so:

1  
Node previousNode;


Everytime we move to another node, the one we just left gets set on the one we just moved to. This means when we build the waypoints we do the following:

1  
2  
3  
4  
5  
6  
7  
8  
private Path recreate(Node node) {
      Path path = new Path();
      while (node.getPreviousNode() != null) {
         path.addWaypointToStart(node);
         node = node.getPreviousNode();
      }
      return path;
   }


Was getting stuck in this while loop because I was not nullifying the previous node in the nodes that I used.

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #11 - Posted 2014-03-20 19:02:01 »

You don't have to keep track of this 'previous' node (it's highly bug prone to do so)

Just look at all connected nodes from the current node, and pick the one with the lowest accumulated cost, until you found the origin.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #12 - Posted 2014-03-20 20:53:47 »

this has been driving me nuts for 3 days. I found the problem.

Dude, you must learn to use the debugger.

1+1=2
Offline Gibbo3771
« Reply #13 - Posted 2014-03-21 04:53:25 »

You don't have to keep track of this 'previous' node (it's highly bug prone to do so)

Just look at all connected nodes from the current node, and pick the one with the lowest accumulated cost, until you found the origin.

I will make it better in the future, as of now I an just seriously happy to have it working being honest. Thanks for the advice, later I intend to add such things as terrain value and such, so it will need refractored.

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
Offline Sabomoth

Junior Member


Medals: 1
Exp: 2 years



« Reply #14 - Posted 2014-03-21 05:07:44 »

Haven't read everything, but if you think it is looking trough too many nodes and taking too long, try looking into Jump Point Search.

http://harablog.wordpress.com/2011/09/07/jump-point-search/
Offline Gibbo3771
« Reply #15 - Posted 2014-03-21 06:49:33 »

Haven't read everything, but if you think it is looking trough too many nodes and taking too long, try looking into Jump Point Search.

http://harablog.wordpress.com/2011/09/07/jump-point-search/

Currently as it is, with 15 enemies all heading towards a player position, it is pretty much instantaneous, that is with 70 tiles between start and dest, so checking 280 nodes. When I don't it with 150 tiles and 30 enemies it hung for about 4-5 seconds since it runs on the render thread. But won't ever have that many entities trying to path find.

Thanks for the link Cheesy, I've looked it different tyoes of search, this one Defo looks good for speed.

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
Offline Roquen
« Reply #16 - Posted 2014-03-21 08:04:11 »

As an aside: no preprocessing techniques seem to get the lion's share of attention where proprocessing methods are drastically faster (frequently exponentially).  As an example if you want any-angle, then it's hard to beat navigation meshes.
Offline Gibbo3771
« Reply #17 - Posted 2014-03-21 08:34:38 »

As an aside: no preprocessing techniques seem to get the lion's share of attention where proprocessing methods are drastically faster (frequently exponentially).  As an example if you want any-angle, then it's hard to beat navigation meshes.

Got an article on that? I'm just diving into the world of AI and pathfinding is the first of many things I would like learn.

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
Offline Roquen
« Reply #18 - Posted 2014-03-21 08:58:46 »

Just do a search on navigation mesh.  A popular C++ library is recast detour.  I'd expect that some of the java higher level libraries have navmeshes.  The basic idea here is that instead of a uniform grid to represent walkability you have connected polygons.  The speed comes having way less data to investigate potentially plus a waypoint graph for even larger deductions.
Pages: [1]
  ignore  |  Print  
 
 

 

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

The first screenshot will be displayed as a thumbnail.

atombrot (26 views)
2014-08-19 09:29:53

Tekkerue (24 views)
2014-08-16 06:45:27

Tekkerue (23 views)
2014-08-16 06:22:17

Tekkerue (13 views)
2014-08-16 06:20:21

Tekkerue (20 views)
2014-08-16 06:12:11

Rayexar (58 views)
2014-08-11 02:49:23

BurntPizza (38 views)
2014-08-09 21:09:32

BurntPizza (30 views)
2014-08-08 02:01:56

Norakomi (37 views)
2014-08-06 19:49:38

BurntPizza (67 views)
2014-08-03 02:57:17
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

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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!