xcuse my absence here (i was formaly invited) But i had no web connection in the last 1 1/2 months and will not have one for the nexttime. I also post now before having read the thread to the end because i dont know how much time i have.
[edit]By the way i think a platform independend implementation would be needed.
The "world-tiles" should be modify-able in a way that new "flags" can be added flexible. The flags would be handled like in a sql DB with "type" and "set" attributes plus the id of the tile as primary key. This could be very handy for new travel methods and new obstacle variants.
[/edit]
Not only are rectangles the most common thing people build in DF their also efficient at covering the unmodified terrain as well and are much simpler to set up and can aid in doing multi-tile creatures as we can be assured that a creature thats longest dimention is shorter then the rects shortest can move through the rectangle.
Rectangles also would support a simple idea i had a bit Better. A little discussion about shading gave me it. Idealy The shortest connection between two (not moving) points is a straight line. Since we know the accesnodes between two mapchunks/Leaves we could use Bresenhams algorithm to calculate The shortest way in a leave betwee two nodes. If a soft obstacle, like a dorf is on the path we can use at this point a short A* to path around the obstacle to continue the precalculated path or we just dodge (1 step forward in a certain angle) and use a bresenham again.
3D paths ("cubes" instead rectangles) like for swimmers/flyers can also make great us of that because the bresenham would return a (in
99% a good part of cases perfect) valid path in the box/rectangle which should be in 90% of all cases faster calculated then a path by a* . Apart from bresenham we could also use bezier curves for a more natural flight/swim behavior.
qoute by DeathofRats
That's part of the problem, and why I'd say it's important for whatever algorithm is chosen to have two characteristics: that segmentation works locally (i.e., I just mined a tile, I don't have to recalculate all the pathing for the whole damn world), and that different areas can be re-zoned (divided or merged). If those two criteria are met, it shouldn't be a problem to deal with terrain modifications.
In my opinion we should implement apart from heuristics multiple takes on (in mapchunk) pathing because depending on the pathing task and outer influences (like the sidelenghts/radius of a mapchunk) a different pathing variant could be more efficient then the usual one. For example bresenham might be enought to traverse 3 mapchunks and in the 4rd a A* might be needed.
AI settlements will need to be generated with their own set of room definitions, traffic designations, etc.. That will break save compatibility again, so it's not trivial - but something like that has to happen if the townsfolk ever are not to act like they all suffer from terrible amnesia, don't really know what they're doing there, and just amble around wondering whether they are just a randomly generated npc in a big simulation.
Actually the save-comp doesnt need to be destroyed. IIrc for villages the "room-devs" already exist and the "paths" could be saved in a own file which actually would also benefit the ADV mode because then the paths for the Ai-Agents "ofscreen" can be still calculated without loading the entire junk of data like objects (not needed items, animals, etc.).
Since the rooms already exists the routes could be caculated on the first load of an old save-file.
[...] more in a bit, feel free to discuss in between. thats it for now