Efficient pixel based pathfinding.

[AwesomeCool]

I was curious if any of you guys have any ideas for efficient pixel based pathfinding. 

Currently I am converting the screen to 32x32 squares (anything smaller causes massive lag). Secondly I apply a A* algorithm to the squares, before I turn the tiles back into pixels. Finally I check the last square the enemy ends up on for ranges and accuracy.

The limitations of this system bug me (barriers have to be divisible by 32) and would at least like to hear of a more efficient algorithm for pathfinding than A*  so I can go to at least 16x16 tiles.

Any suggestion, thoughts, or ideas you would do in this situation?

I was thinking of doing a 32x32 Based path finding test, and then shrinking down the range of tiles picked for pathfinding based on 16x16 tiles.  I don't know if that would make a big difference though.

 

[Zeriab]

Perhaps a hierarchical approach such as the HPA* algorithm can be helpful.

*hugs*

 

[AwesomeCool]

That sounds incredibly awesome.

I shall attempt it.

 

[♥SOURCE♥]

What exactly are you trying to do? There's probably a better way. Most of the times you don't actually need pixel precision and you can get away with using waypoints or a more efficient map representation to perform the search on.

 

[AwesomeCool]

It is for my battle system, which allows enemies and actors to move around the battle scene.

 

[♥SOURCE♥]

Okay, why do you want pixel precision for it?

Would your battle system have any solid object or enemies that would create a structure that a simple moving method like the one used in RM default's move_toward_character wouldn't be able to solve?

If you provide more details regarding your idea for the battle system, I'm sure others will be able to provide better suggestions.

 

[AwesomeCool]

It has user definable barriers on the field in which certain enemies/actors cannot pass and each turn the enemy can move with in a ellipse around himself.  Enemies collide with each other. It is turn based.

 

[♥SOURCE♥]

Okay, what is the smaller collision box size that you have planned?

 

[AwesomeCool]

4x4 to 16x16

 

[Zeriab]

An alternative approach can be to represent collision boundaries as convex polygons.

There is a lot of existing theory about convex polygon collision detection and intersection.

I would expect a cost of even higher complexity than with the HPA*, and the imprecise nature of floats will also introduce their own type of fun.

Depending on your world you may to represent it with very few polygons. And I suspected the sparsity and required frequency of collision detection is significant from a performance perspective. That is just a gut feeling so don't trust too much.

*hugs*

 - Zeriab

 

[Quxios]

I've been working on a pixel based pathfinding for a couple of weeks now.  From most of my tests I've managed to cut down a path from taking 100+ seconds down to only 1-2 seconds.  What I did was just instead of checking collisions at every pixel, I would move in a grid which was related to the objects bounding box.  By doing just this it got cut down to around 0.6 seconds, but the problem with this is that now you're moving in a grid and it might not find a small path that it should have been able to fit in because its moving on a grid and it didn't fit in.  So what I did for this was make it treat only collision edges with pixel precision while open spaces are treated as a grid.  Of course this increased the time up to around 2-3 seconds.  But that's still a huge performance change!  

Very bad video of the tests from that paragraph

I'm still trying to optimize this even more by trying to add in HPA* like Zeriab suggested, I've also tried to optimize it with jps since I have read using jps with A* is very optimized, but I just couldn't get that to work and felt like it made it was heavier then just A*

 

[♥SOURCE♥]

I've been working on a pixel based pathfinding for a couple of weeks now.  From most of my tests I've managed to cut down a path from taking 100+ seconds down to only 1-2 seconds.  What I did was just instead of checking collisions at every pixel, I would move in a grid which was related to the objects bounding box.  By doing just this it got cut down to around 0.6 seconds, but the problem with this is that now you're moving in a grid and it might not find a small path that it should have been able to fit in because its moving on a grid and it didn't fit in.  So what I did for this was make it treat only collision edges with pixel precision while open spaces are treated as a grid.  Of course this increased the time up to around 2-3 seconds.  But that's still a huge performance change!  

Very bad video of the tests from that paragraph

I'm still trying to optimize this even more by trying to add in HPA* like Zeriab suggested, I've also tried to optimize it with jps since I have read using jps with A* is very optimized, but I just couldn't get that to work and felt like it made it was heavier then just A*

A possible (and huge) update would be to perform the search in a 32x32 pixels grid, but make an additional (and special) passability check if the regular one returned false. That way, when it encounters an impassable tile, it would "make sure" that it is really impassable for the character's bounding box. No need to make it treat each pixel as a node.

The map representation is one of the things that have a huge impact on the performance of any search algorithm implementation, it directly correlates to the number of operations the algorithm would have to perform each iteration. Considering each pixel as a node is a very bad idea.

Before even considering any other improvement or optimization technique, you should look at the map representation.

My advice would be to focus on getting a decent A* using the method I suggested, HPA* would only make things complicated for you (how would you define "rooms" and entrance/exit points if you plan on releasing it for public usage? would you include an editor for it? all that trouble just to get agents to move in an area that fits in the default screen size?) and JPS wouldn't yield much of an improvement if your map representation uses pixel sized nodes.

How do you know when it is good enough? What to aim for? Anything above 0.01 seconds for a path that completely fits in the screen size wouldn't be acceptable if you plan on using the pathfinder often and for larger "distances".

Let me know if you have some specific questions

 

[AwesomeCool]

@Quasi 1 second is too long for path finding. I would convert the grid into tiles like source said and then when it gets close to target shrink the tiles to get a more accurate position (I have it really really fast this way).

@Source I like your idea, but how would you go about marking an impassible square in the first place without slowing the game down?

 

[♥SOURCE♥]

@Source I like your idea, but how would you go about marking an impassible square in the first place without slowing the game down?

You could perform one iteration at start through the barriers you mentioned, check which 32x32 pixels nodes are touched by each corner of each barrier (or impassable thing), mark that as impassable using a table, array, hash or your desired data structure. Do the same for the characters each time the pathfinder is about to perform a search (since you probably won't have more than 20 enemies in the battle screen at any time, it's okay). 

You can also do it each time a search is about to occur for the barriers, in case you don't want to update the used positions each time one is destroyed to mark them as passable.

When the search checks for passability, that marked tiles would tell it "stop! this tile/node and its surroundings require a special passability check" and you would perform a check to see if anything in that tile or its neighbors would make it impossible for the character that requested the path to pass (taking into account, of course, the direction the character would be coming from and the direction it is heading to).

The same approach can be used to handle pixel-movement collision detection in a much more effective way.

 

[AwesomeCool]

Thanks source. 

I think I know what to do now.