Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (475)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (530)
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 optimization.  (Read 3408 times)
0 Members and 1 Guest are viewing this topic.
Offline Gudradain
« Posted 2011-08-06 14:23:27 »

I have some hand made pathfinding code and I wonder if it could be more performant.

Currently I'm finding a path on a 200x200 (40000) grid map in approximatively 50 ms in worst case scenario. Does anyone get better result with pathfinding? Would really like to improve my code.

Of course, I have a lot of otimization where I can reduce the number of cell in the map and get the same result but I would like to see if I can improve the size of the map and get the same result.

N.B. : For comparison, I benchmark the difference in speed between my implementation and the one that come in Slick and mine is faster by 64 times. (Maybe I did something wrong with slick one but that's what I got)

N.B2 : An early version of my code can be see here. I currently swap the arrayList of open nodes by a MinHeap to get a boost in speed by 10 times.
Offline pjt33
« Reply #1 - Posted 2011-08-06 17:08:53 »

Why don't you post the current code? Hard to tell whether it can be improved without seeing it.
Offline Gudradain
« Reply #2 - Posted 2011-08-06 17:19:29 »

Why don't you post the current code? Hard to tell whether it can be improved without seeing it.

http://code.google.com/p/protectcastle/source/browse/pathfinding/pathfinding/grid/astar/GridAstar.java
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline krasse
« Reply #3 - Posted 2011-08-06 22:34:52 »

I optimize my A* with a lookup table that is filled in after each path. This method assumes static obstacles and not to many cells/nodes since the algorithm uses N^2 space.
After one A* search, each subsequent search (involving any of the nodes in the found path) only takes linear time in number of nodes on the optimal path.

The lookuptable[fromId][toId] contains the ID (or index/reference) of the next node on the optimal path from fromId to toId. When you get an optimal path, you can update the table for each node on that path in L^2 time where L is the number of nodes on the path.

When you want a path from A to B you check the lookuptable[A]
If the ID exists you get that A' and continue with A' = lookuptable[A'] until you get A' == B and you collect all the node IDs during the search.

Offline Gudradain
« Reply #4 - Posted 2011-08-06 22:43:14 »

I guess lookup table could work since the world is not changing that often. Only placing a couple of building some times.
Offline krasse
« Reply #5 - Posted 2011-08-06 22:58:27 »

I guess lookup table could work since the world is not changing that often. Only placing a couple of building some times.

The problem with a changing world is that you have to invalidate all stored paths in the lookup that involve the newly occupied cells or do something more fancy Smiley

Offline Gudradain
« Reply #6 - Posted 2011-08-15 06:47:38 »

Thanks for the idea krasse.

I guess I should have thought about it sooner but since my game is a tower defense all unit go to the same point so I can precalculate easily the path for each node.

Before : 50 ms for a 200x200 map
Now    : 0.04 ms for a 200x200 map

The only draw back is that it takes around 50 ms to precalculate every path and you must do it everytime that you place or remove a building. But that is a lot faster Smiley
Offline theagentd
« Reply #7 - Posted 2011-08-15 08:55:40 »

Krasse, that is not correct. You have to recalculate the paths every time you place or destroy/sell a building, as that could give a shorter path to the target.

Myomyomyo.
Offline pitbuller
« Reply #8 - Posted 2011-08-15 09:00:52 »

Some fancy way would be find all paths that include edited cell and only update those paths. Bad thing is that the worst case scenario is then even heavier and that can happen very often.
Offline krasse
« Reply #9 - Posted 2011-08-15 10:15:08 »

Krasse, that is not correct. You have to recalculate the paths every time you place or destroy/sell a building, as that could give a shorter path to the target.

Yes, you are right when it comes to destroying/selling buildings but you can still do this when you place a new building (unless it is a bridge or something that opens up new travel paths). It might be very expensive though as pitbuller pointed out Smiley

BTW, I am happy that you were able to optimize your pathfinding Gudradain!

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Gudradain
« Reply #10 - Posted 2011-08-15 18:01:08 »

yeah, tower defense is a very specific type of pathfinding were your end destination almost never change so this optimization was possible here.

But I'm thinking another place where this sort of optimization would be really usefull : RTS with gathering unit. Those unit almost always come back to the same base to bring back their resources. So for each resource base you can precalculate a distance map and then use this pathfinding method. The resource bases almost never change their location once placed so you don't need to calculate the distance map very often and after that pathfinding for the unit bringing back their ressources to that base is almost instant (0.3 ms on a 1000X1000 map from the testing I did so far).

This way the only sort of pathfinding that is still expensive are the attacking unit that you control. That should make it lot easier to deal with pathfinding performance in an RTS or similar game.
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11


Game Engineer


« Reply #11 - Posted 2011-08-15 19:23:42 »

Some fancy way would be find all paths that include edited cell and only update those paths. Bad thing is that the worst case scenario is then even heavier and that can happen very often.
How could you even do this? Just solving one single time with A* shouldn't be very expensive (50ms seems very expensive, btw, unless you have a massive grid, I'd double check your heuristic is working correctly). And once you change the grid in any way whatsoever you need to recalculate absolutely every path that may involve that space... and I can't think of any way to know for sure whether a path involves it.

The only things you could do, as far as I can think of, is do a partial A*, that is if the full path is from A to Z and you remove a building a M, do a pathfind between J and Q, and replace that portion of the path. The drawback is that this might not get the best solution, though. Another option is to make "mipmap" equivalents for your grid, and pathfinding within that. i.e. divide your grid into several different-sized grids. So like if you have a 100x100 maze, have a 10x10 representation of it, a 25x25, a 50x50, and finally the actual 100x100 grid. Each grid space in the 10x10 actually represents 100 grid spaces, in the 25x25 16 spaces, in the 50x50 4 spaces. As entities are built or removed, you not only update the 100x100 grid, you also update the larger grids. If anything at all exists in those 100 spaces for the 10x10, it's considered a full space. So what you do is try to pathfind on each level, starting with the 10x10 down to the 100x100. You can extrapolate what an empty space means in any one of the grids, even if you can't compute a full path with it. Like if there is an empty space in the 10x10, that means everything in that 100 space area in the 100x100 is empty so you don't need to pathfind through the whole thing. It's pretty complicated and easy to mess up, but can help in certain situations. Still, if you're doing tower defense, I imagine that when you really need to get the pathfinding fast (when the whole screen is filled) it's actually going to slow you down because you'll start doing a bunch of redundant checks....

So in conclusion I'd just figure out why your algorithm is slow and rerun it whenever a building is plopped down. Tongue

See my work:
OTC Software
Offline Gudradain
« Reply #12 - Posted 2011-08-15 21:08:38 »

Some fancy way would be find all paths that include edited cell and only update those paths. Bad thing is that the worst case scenario is then even heavier and that can happen very often.
How could you even do this? Just solving one single time with A* shouldn't be very expensive (50ms seems very expensive, btw, unless you have a massive grid, I'd double check your heuristic is working correctly). And once you change the grid in any way whatsoever you need to recalculate absolutely every path that may involve that space... and I can't think of any way to know for sure whether a path involves it.

The only things you could do, as far as I can think of, is do a partial A*, that is if the full path is from A to Z and you remove a building a M, do a pathfind between J and Q, and replace that portion of the path. The drawback is that this might not get the best solution, though. Another option is to make "mipmap" equivalents for your grid, and pathfinding within that. i.e. divide your grid into several different-sized grids. So like if you have a 100x100 maze, have a 10x10 representation of it, a 25x25, a 50x50, and finally the actual 100x100 grid. Each grid space in the 10x10 actually represents 100 grid spaces, in the 25x25 16 spaces, in the 50x50 4 spaces. As entities are built or removed, you not only update the 100x100 grid, you also update the larger grids. If anything at all exists in those 100 spaces for the 10x10, it's considered a full space. So what you do is try to pathfind on each level, starting with the 10x10 down to the 100x100. You can extrapolate what an empty space means in any one of the grids, even if you can't compute a full path with it. Like if there is an empty space in the 10x10, that means everything in that 100 space area in the 100x100 is empty so you don't need to pathfind through the whole thing. It's pretty complicated and easy to mess up, but can help in certain situations. Still, if you're doing tower defense, I imagine that when you really need to get the pathfinding fast (when the whole screen is filled) it's actually going to slow you down because you'll start doing a bunch of redundant checks....

So in conclusion I'd just figure out why your algorithm is slow and rerun it whenever a building is plopped down. Tongue

I always have the same destination since it is a tower defense game. So I just need to calculate every paths for one cell. It's fast. In fact, it's as fast as the calculation of normal A* in worst case scenario (where you iterate through all the cell in the map).

I don't think that my code is slow, in fact I couldn't find one that is faster for now. Still, I would gladly have an example of faster code so I can improve. Your Ah!Maze example seems to take forever to run even when you try to reduce the draw delay to 0. Didn't check the source code to see if it has speed limitation in it to help for example purpose though.

I thought a long time about mipmap but those seems pretty complicated to get right. The problem is that removing or adding a building in one mipmap cell doesn't affect only that mipmap but the whole map as that would create new possible path or remove previous one.
Offline pitbuller
« Reply #13 - Posted 2011-08-15 21:18:47 »

Gudradain have done wonders with pathfinding. Our game run now almoust full fps at cell phone(crappy one) before any optimizations to rendering or other game logic.
Offline Gudradain
« Reply #14 - Posted 2011-08-15 21:25:58 »

Thx for frustrating me Eli.

To calculate the distance map on a 200X200 map it takes 15 ms instead of 40 ms now.
Online Riven
« League of Dukes »

JGO Overlord


Medals: 742
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #15 - Posted 2011-08-15 21:52:07 »

If all weights are equal, you're probably using a floodfill that tags each cell with an age and call it a day Smiley

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline pitbuller
« Reply #16 - Posted 2011-08-16 08:25:59 »

If all weights are equal, you're probably using a floodfill that tags each cell with an age and call it a day Smiley
Could you explain more? I did't quite understand.
Online Riven
« League of Dukes »

JGO Overlord


Medals: 742
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #17 - Posted 2011-08-16 09:34:06 »

Use a pathfinder without a target: it will flood the entire area. Using the data in the nodes, you can then backtrack from every cell.

To optimize the end result, you can make a byte[] that holds a value 'pointing' to the neighbouring cell that is closer to the 'target' (tower?).

To backtrack, you can simple lookup the value in the grid, and jump through it, without any logic for finding the optimal backtracking path.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Gudradain
« Reply #18 - Posted 2011-08-16 19:23:57 »

That's exactly what I'm using right now Riven. It's pretty fast. It never take more than a few micro seconds.

But my old pathfinding code was also using backtrack but without a flood fill. Since the destination change each time I need to calculate enough of the distance map to reach my destination. Than I was backtracking from my destination toward my current location to get the path.

Currently, the code only work for one destination but I could probably change it so it work for many destination. I would have to store a list of distanceMap (one for every cell) it could be pretty long :S. But if I calculate only the map that are required it could be faster.

EDIT : Although it doesn't matter if the node are not weighted equal. My floodfill algorithm is A star where the heuristic always return 0.
Online Riven
« League of Dukes »

JGO Overlord


Medals: 742
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #19 - Posted 2011-08-16 19:28:25 »

Currently, the code only work for one destination but I could probably change it so it work for many destination. I would have to store a list of distanceMap (one for every cell) it could be pretty long :S. But if I calculate only the map that are required it could be faster.

It's extremely easy. Just start your search from multiple sources. I use a strategy like that to enable quickly finding the shortest route between N start points and M end points. (which lumberjack is closest to a tree)

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11


Game Engineer


« Reply #20 - Posted 2011-08-16 19:29:17 »

Haha, glad I could help, Gudradain. Smiley And yeah, Ah Maze is very slow, it is optimized in no way whatsoever and it slows itself down (even with 0) for demonstration purposes. I have many much faster algorithms hanging around but I don't think I put them anywhere. But I wasn't saying that you were doing anything "wrong," your algorithm looks fine to me at a cursory glance. I was just saying that your time was too long, and seemed like it could be sped up. I will be one of many to say that premature optimization is pointless, and I definitely wasn't judging in any way by you having a slower algorithm.

See my work:
OTC Software
Offline Gudradain
« Reply #21 - Posted 2011-08-16 19:55:39 »

It's extremely easy. Just start your search from multiple sources. I use a strategy like that to enable quickly finding the shortest route between N start points and M end points. (which lumberjack is closest to a tree)

Are you doing some sort of RTS? (the lumberjack cutting tree thing). I figured that was the best approach for gatherer that always return the resource they collect to the same base (same destination = only 1 distance map).

Haha, glad I could help, Gudradain. Smiley And yeah, Ah Maze is very slow, it is optimized in no way whatsoever and it slows itself down (even with 0) for demonstration purposes. I have many much faster algorithms hanging around but I don't think I put them anywhere. But I wasn't saying that you were doing anything "wrong," your algorithm looks fine to me at a cursory glance. I was just saying that your time was too long, and seemed like it could be sped up. I will be one of many to say that premature optimization is pointless, and I definitely wasn't judging in any way by you having a slower algorithm.

No prob Smiley. Just a question, you talked about mipmap. Was it just an idea out of the blue (something theoric) or you have actually seen it working with better performance than other form?
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11


Game Engineer


« Reply #22 - Posted 2011-08-16 20:32:51 »

No prob Smiley. Just a question, you talked about mipmap. Was it just an idea out of the blue (something theoric) or you have actually seen it working with better performance than other form?
It's an idea I've thought of trying a number of times but never have, and as far as I know there aren't any games that have used it. In situations where there is a lot of open area (like Starcraft) I could see it making sense, but I've never made a game where it's a good option.

See my work:
OTC Software
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.

ctomni231 (33 views)
2014-07-18 06:55:21

Zero Volt (29 views)
2014-07-17 23:47:54

danieldean (24 views)
2014-07-17 23:41:23

MustardPeter (26 views)
2014-07-16 23:30:00

Cero (41 views)
2014-07-16 00:42:17

Riven (43 views)
2014-07-14 18:02:53

OpenGLShaders (31 views)
2014-07-14 16:23:47

Riven (30 views)
2014-07-14 11:51:35

quew8 (29 views)
2014-07-13 13:57:52

SHC (64 views)
2014-07-12 17:50:04
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
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!