Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Refar]

Somehow i am sure this was talked before... Thgen again - i can't find nothing neither in form nor in the development goals...
As pathfinding is causing a lot FPS loose on bigger fortresses... To me it started quite fluid and become unplayable at about 100 Creatures (~80 Dwarfes + a few pets).
I.e. outdoor activities (plant gathering, tree choping) seem immensely slowing down...

How does it work right now ? Tile based ?

Maybe allowing (forcing ?) the player to set waypoint areas (similar to rooms) + using exising rooms a waypoints anyway, and then let pathfinding run on these waypoints might help reduce the complexity of pthfinding a lot.

[Core Xii]

You can already do that by marking the most-used areas with the high traffic designation and least-visited dead-ends with the low traffic designation. This causes the pathfinding to explore the most-visited areas first, reducing the amount of explored tiles.

[Refar]

Yes, i did that and it helped a bit, but not nearly enought.

What i mean is use these designations/waypoints as basic units in the pathfinging algorithms, to reduce the overall complexity by a huge factor - make your path decision threes for a given area much smaller (similar to how it is done for example on bot pathfinding in huge 3d game environments).

Say you have a 100x100 tiles floor divided in 10x10 regular rooms. Room/WP based path finding will give you 100 nodes - one per room - while tile based end up with 10000. This is quite a difference.
Inside one room / node you could drop most of path finding at all and just utilize a greedy "move towards target" approach.

This could cause trouble in some rooms, but if the player is alowed to set waypoint areas, he can easyly fix any waypoints that might cause locks.

[catpaw]

We just had a descission exactly for this: http://www.bay12games.com/forum/index.php?topic=24615.0

Yes, a "spanning tree" solution would IMHO be another approach that looks just good/bad doable as the ant-like auto-signalposts. This ideas IMHO remind of the Spanning Tree Protocol ( http://de.wikipedia.org/wiki/Spanning_Tree_Protocol ) of networking

[Refar]

Nuts. Missed the other thread.

And yes this comes from graph driven algorithms. Not necessarily spanning tree tho - there are better ones if just a path is asked for.

And yes this is not the only possible solution - the main boon here imo - it is easy to understand, transparent for the user and simple to implement. Also with good waypoints it should be very close to actually finding optimal paths.

The Ant one might run faster in the end.

In any case the difference to the complete search - which has exponential running time - anything polynomialy bound would be a step forward, that should allow a dramatic increase in population without boging down the frame rate.

I will move other to the other thread, so all the path finding rant is conviniently in one place