Pathfinding

Started by B@R5uk, April 10, 2020, 09:32:28 AM

Previous topic - Next topic

k2ymg

I made a pathfinder mod with basic A*. It is always takes best path. I'm not feel any lug, but I didn't test other env., like laptop, linux or mac. (I use Core i7-4771, 3.5GHz.)

Also, I made a A* with region-to-region cost calculation. It was not best, but better than vanilla. However, it was bad performance. To do R-to-R efficiently, we need modify Region class but we can't.

Anyway, if you use modern pc, basic A* is not bad.

wwWraith

The 2 main problems of the simplified algorithm (using some regions instead of single tiles) are that if some region has a lot of obstacles (e.g. stockpiles, rooms with furniture, trees alongside a road), it sees its movement penalty as high in average and will avoid to cross that region at all rather than trying to find a clear way through it; and probably it sets transitional waypoints to the centers of those regions, thus zigzags.

What about trying a compromise: calculate a "rough" path at long distance using that (or any other?) simplified algorithm, then choose some point on it about 20 tiles from the start and calculate an exact path to it using the "honest" algorithm; then, when the pawn moves some tiles (10-15 - the idea is that the pawn won't yet enter the region to which that transitional point belonged; probably it'll be easier to do just every few seconds), repeat it, finding a new simplified path from the current position and a new transitional point 20 tiles away, etc. This way the pawn will always move on exact segments, reducing said problems (especially the second one, because the pawn will never be forced to go to those regions' centers or whatever).

If my description is not clear enough but anyone is interested, I can try to explain better.
Think about it. Think around it. Perhaps you'll get some new good idea even if it would be completely different from my words.

LWM

The approach I had envisioned was something like this:

Make a bunch of regions (where everything in a region is roughly reachable from elsewhere in the region).  For each region, calculate the distance from one neighbor to another, cache the data with the region.  Calculate distance using region-traversal calculations.

You'd still need some basic estimate, which will still cause problems in some cases, but ?

wwWraith

I'm afraid this "adaptive" regions division might be even harder to code and more resource hungry (it will require frequent map-wide recalculations, ideally with any change on map including moved items). And there still will be problem with finding what points inside those regions should be used transitionally.
Think about it. Think around it. Perhaps you'll get some new good idea even if it would be completely different from my words.

LWM

I had been assuming that it would only recalculate regions when things pawns cannot cross get built.

LWM

Would you be interested in sharing your code, by the way?

wwWraith

Unfortunately I still didn't learn C#, thus no real code :(
Think about it. Think around it. Perhaps you'll get some new good idea even if it would be completely different from my words.

Canute

Joint venture, wraith try to write down the algorithm in some mathematical forumla and LWM could try to put it into some C#.