Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (736)
Games in Android Showcase (224)
games submitted by our members
Games in WIP (814)
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  
  Adventures in Pathfinding  (Read 1097 times)
0 Members and 1 Guest are viewing this topic.
Offline Gilmok

Innocent Bystander

« Posted 2017-08-18 22:36:30 »

Pathfinding is a large topic as it takes up a large amount of CPU so I wanted to just talk about some things I've been doing to speed up pathfinding for an RTS game I am making.

We all know and love A*, but we do not love its speed.  We know that A* is n^2 over the number of nodes that it expands.  The only thing you can do at this point is seek to reduce the n.

I began with Jump Point search, looking carefully at what points were jump points and which were not.  I found that tiles next to convex corners became my jump points.  My tiles use 4 borders passage (tiles are not just open-closed but have open or closed openings on each of the 4 sides), so some other points also became jump points.  I wrote a function to calculate when a tile gains and loses jump point status based on which of its borders are open.  Now instead of a graph consisting of every tile it just consisted of these jump points.  I built a navmesh of these, which is updated every time a tile gains or loses jump point status.

For a faster jump point search, all tiles have a distance value in all 8 directions to either a wall or a jump point.  Testing adjacency involves dividing the path into diagonal and straight line components and comparing distances (as opposed to walking to each tile and seeing if you hit a wall).  This required me to write methods to update each tile distance whenever a wall or jump point was placed and/or removed.

At this point pathfinding has 2 major costs: finding the isovist (which is the list of jump points that the starting location is adjacent to), and finding the path.  I started with a bi-directional search but I found that finding the isovist was about the same cost as finding the path, so I went back to single direction.  Also, I often have a situation where the starting point is adjacent to hundreds of other points but only few of them actually yield a good path.

To improve the starting point situation,  I divided each point's list of adjacent points into 8 wedges, like a pie.  Every time I expand a node, instead of fully expanding it, I just expand the wedge that contains the best angle to the end point.  As I ran out of nodes in that wedge, I would move around to surrounding wedges.  Now, the A* algorithm works by costing each adjacent node, putting each node into the open list, and selecting the best to expand.  I found that wedging didn't get better performance until I only costed the nodes in the wedge.  This means that I won't always get the best path.  However, my testing shows that the deviance from the best path is usually very small on sparse graphs (0.04 tiles on average) while cutting pathfinding time by a factor of 4. 

I also did try to tackle finding the isovist faster.  The naive approach is to just test the adjacency of each jump point to the starting point.  I also began this other, more involved approach using Formations.

Each jump point on the map is next to a formation (which is an obstacle - think of a rock formation).  To get the formation that a jump point is next to you need to trace out the formation from the navmesh.  To do that you start at a point and use the 8 distance markers in each tile to trace around the edges of the formation until you return to your starting point.

Now that you have all the formations traced out, you can draw a box around them.   This formation list is updated every time you update your graph.

To get the staring point's isovist, cast a beam in all 8 directions.  To cast a beam up, for example, you need the up-right and up-left distances in the tile.  The start of the beam is the tile's x minus the up-right distance, and the beam's width is the up-right distance plus the up-left distance.  Cast this beam up to the top edge of the map (draw a box).  Find all formations that lie in that box, then sort them according to their bottom edges.  Create a bit field containing the visibility lanes in the beam, then eliminate the visibility lanes of each formation in the list.  Record the formations that did hit (and eliminate) visibility lanes.

Repeat the above process for all 8 directions, adding only unique formations.  Then test the adjacency of each point in only the formations you found.

My initial run of this process was quite slow, namely because I was testing the beam against each formation.  My CS program didn't have a class in computational geometry.  After further research I have read about using interval trees, which could be a promising approach to test the collisions between each formation and beam.

Congratualtions for reading this far.  Perhaps you can benefit from my journey in climbing the pathfinding Mt. Everest.
Pages: [1]
  ignore  |  Print  

cybrmynd (138 views)
2017-08-02 12:28:51

cybrmynd (159 views)
2017-08-02 12:19:43

cybrmynd (153 views)
2017-08-02 12:18:09

Sralse (169 views)
2017-07-25 17:13:48

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

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

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

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

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

Rule (1312 views)
2017-03-19 12:42:17
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!