A pathfinder that may be good for spring

[tizbac]

The main difference is that this supports full 3d.

A good implementation maybe splitting map in small tiles and updating them as the map changes ( detour supports pathfinding across tiles ).
this will allow also having walkable buildings and true transports with some other modifications. All you need is just passing entire mesh ( buildings included ) to recast and it will generate the navmesh.

Kloot: you have to generate a navmesh for each moveable unit cause the navmesh is for a specific agent radius and height

[SeanHeron]

Kloot, I think echoone was referring to the projects/recastnavigations implementation of pathfinding (not Springs). I think you addressed the question (wrt time) yourself in this:

Finding a path across a navmesh would be cheaper (depending on mesh density) than across a waypoint graph, but that is not even a bottleneck *now*.

This is sidetracking a bit, but something I've wondered since reading the dev chat (rr pathfinding and more), was whether not updating for dynamic terrain (ie as an option a game could set) might be possible after refactor? My thinking was that some games(makers) might rather have units taking slower path over (new) craters than incurr performance hit due to recalculations.

Not that I really have an idea about any of this, though...

[echoone]

So what currently takes the path estimator during start up many seconds can likely be done in a fraction of a second?

No.

Constructing a navmesh for every movetype (!) from the heightmap and keeping each up-to-date with dynamic terrain deformation is not "fraction of a second" territory.

Ouch. I forgot about that. So using his 303ms (IIRC) example, on that map, we're really looking at something like 300ms x each move type (ground, water, hover, and air; or roughly 1.2s), with an update mandatory every time deformation occurs? Plus tile updates for wreckage and new construction? Eeek!

Finding a path across a navmesh would be cheaper (depending on mesh density) than through a waypoint graph, but that is not even a bottleneck *now*.

Path estimation in Spring IS A*. Therefore, O(N log N).

Ya, I knew what Spring uses. I was trying to better understand the pros and cons of recastnavigation versus the current astar.

Thanks Kloot.

[echoone]

The main difference is that this supports full 3d.

A good implementation maybe splitting map in small tiles and updating them as the map changes ( detour supports pathfinding across tiles ).
this will allow also having walkable buildings and true transports with some other modifications. All you need is just passing entire mesh ( buildings included ) to recast and it will generate the navmesh.

Kloot: you have to generate a navmesh for each moveable unit cause the navmesh is for a specific agent radius and height

You posted while I was still crafting my reply above.

For those of us who do not eat and sleep path finding, what are the clear pros and cons of using recast versus astar? I read the following, but I don't see anything which really explains costs which allows for feature/cost benefit analysis versus current astar implementation.

Detour offers simple static navigation mesh which is suitable for many simple cases, as well as tiled navigation mesh which allows you to plug in and out pieces of the mesh. The tiled mesh allows to create systems where you stream new navigation data in and out as the player progresses the level, or you may regenerate tiles as the world changes.

[KaiserJ]

this is very interesting, im googling and struggling to learn the differences and methods

how hard would implementing the method suggested by tizbac be (ofc impossible for me, i just mean generally amongst you skilled programmers and devs)

[AF]

Id like to see more information, is there a demonstration project using the library we can look at?

Im also astonished that people responded the way they did, not because tizbac posted in the way a noob might, but because its glaringly obvious he's more than capable of implementing it himself and he was just asking what we thought about it? Maybe it was a big hint that he's interested in experimenting and wanted to know what we had in mind already?

[tizbac]

there's a demo on the project page that allows you to test interactively obj files

[hoijui]

if you want to safe path-finder costs in regard to map deformations, you have to turn them off. ignoring them is not a viable option. think about 10 adv fusions exploding on soft ground, and you ignore that. the result will not be, that units will take a sightly slower path, but much uglier stuff will happen. it does not need such extreme stuff even. just think of a soft next to a hard ground, and something heavy exploding there.

[tizbac]

just rebuild tiles altered by explosion and you are ok

[echoone]

just rebuild tiles altered by explosion and you are ok

Does that mean if there are 1000 units, that tile must be recalculated 1000 times? A previous comment made me think that's the case.

[tizbac]

not for every copy of the unit , just for types

[tizbac]

Update:
I've found a library that may be suitable to do terraforming and environment destruction on 3d maps : http://www.thermite3d.org/joomla/