A pathfinder that may be good for spring

[tizbac]

I've found that project http://code.google.com/p/recastnavigation/ , they are implementing also multi-agent pathfinding so it'll be ok for an rts, it supports full 3d pathfinding and tiled navmeshes ( so in the case you build something you have just to update a small tile of the navmesh ) , it supports flags and path costs and raycasting to see if pathfinding is necessary or you can just move in the direction of destination point.

[jK]

- don't put up requests for a particular implementation of an idea if you aren't a game programmer.

[Hobo Joe]

You can't just copy-paste pathfinders.

[tizbac]

1. This is NOT a feature reuqest , it's just a suggestion that may help devs
2. I've heard that they are abstracting pathfinder on spring so using it shouldn't be hard

[Forboding Angel]

shouldn't be hard

Go look in a mirror and slap yourself.

[Das Bruce]

Have you done any programming at all?

[Hobo Joe]

1. This is NOT a feature reuqest , it's just a suggestion that may help devs
2. I've heard that they are abstracting pathfinder on spring so using it shouldn't be hard

You're right, it'll be really easy. Why don't you get started then?

[Super Mario]

Well this topic certainly backfires on a user who has a anti-windows for his avatar. Give the spring devs a prototype if you want to try to convince them.

[tizbac]

i'm using it for another project atm , so i have not time to implement it on spring , and with such replies on topics like that i understand why development is stalling ...

[hoijui]

tizbac did some coding for spring already, he does know C++. probably more then most others in this thread.
it is true that we try to abstract the path-finder/-follower stuff, but it is still a long way till that will be usable/nice.

[Masse]

Way to be an ass community! I hope that you guys apologize.

[Forboding Angel]

Was not aware that he has contributed in the past. My apologies. It's jsut that this thread reads like some newbie coming in from <insert game here> saying "OMGOMGOGMGOMGOMGOMGOMGOMG GUYS WE HAVE TO HAVE x FEATURE BECAUSE IT"S AWESOME AND WILL BE EASY!!!!1111oneoneeleven"

[Das Bruce]

Was not aware that he has contributed in the past. My apologies. It's jsut that this thread reads like some newbie coming in from <insert game here> saying "OMGOMGOGMGOMGOMGOMGOMGOMG GUYS WE HAVE TO HAVE x FEATURE BECAUSE IT"S AWESOME AND WILL BE EASY!!!!1111oneoneeleven"

This, pretty much verbatim.

[maackey]

You guys suck.

tizbac never requested anything in his first post (and even reiterated it was not a request in his second) and yet some people just have to come in and start trolling and flaming the hell out of this thread.

You'd rather moan and flame anyone who tries to help than to have something better than the current POS pathfinder that spring has now?!? Gah.

[Das Bruce]

Read the thread again maackey, if tizbac's original posts isn't a feature request then it's the next best thing. He posts a link to something that's been posted before with no discussion of how it would be implemented or much else, so we flipped him off like any noob who can't read the rules. However, once we realised the actual situation we appologised. All this drama occured and was corrected in about half a page. Don't get your panties in a bunch.

[Beherith]

I fully agree with maackey here. Questioning ones coding skills and contributions (tizbac has done a lot of things for spring, I still use his python lobby bot for gargamel and map/mod stats) is poor form.
He merely brought to our attention another open source pathfinding system. It wasnt even posted in feature requests, and I see nothing in the post that could result in it being interpreted as one.

[tizbac]

I've loaded DSD on the demo included on pathfinder sources , this screenshot shows the navmesh
http://img691.imageshack.us/img691/6725/dsdpf.jpg

edit:
tried on my insane map "Speedmaze" ( you can find it on jobjol )
results: http://img828.imageshack.us/img828/2064/speedmazepf.jpg

current spring pathfinder doesn't even reach 1/10 of the map
edit:
note: build time isn't pathfinding time , it's the time needed to create navmesh ( the equivalent of "calculating estimated path costs" currently )

[echoone]

Way to be an ass community!

Couldn't agree more! When people should have simply said, "Thanks!", they yelled, "Get a rope!" Hell, no response at all would of been more polite than what transpired.

And people have trouble understanding why the Spring community is slow to grow...

Even if he had never previously contributed to Spring, attempting to lynch someone for sharing their knowledge is the definition of, "ass." For all you know he could of been a passerby who was willing to implement the feature. Responses like this can easily change people from feeling generous to fleeing with their middle finger erect - and justifiably so!

[echoone]

I've loaded DSD on the demo included on pathfinder
note: build time isn't pathfinding time , it's the time needed to create navmesh ( the equivalent of "calculating estimated path costs" currently )

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

How does actual path finding, time wise, compare with something like astar? Complexity?

Hmmm....oddly enough, the blurb for the project says:

The Library is free for commercial use and open source under the ZLib License.

The project's information says:

Code license: MIT License

* Fixed incorrect terminology.

[Kloot]

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.

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*.

How does actual path estimation, time wise, compare with something like astar? Complexity?

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