*phew*
Update 309Finally I think that everything having to do with AI data being saved to level files is DONE! For each creature (or rather for each "pathing template", some creatures share the same pathing data as their movement is similar) there are now several AI heatmaps that can easily be accessed. One of those is the dead end map, and then there is a dijkstra map for each room exit.
Here's a visualization where I can look at the different AI maps for all the different creatures by moving the mouse around. The ones with little blinking dots are the dead end maps, and the blinking dots are the hub spots or fleeing targets. Saving those to the file was kind of a hassle as well, until I figured out I could just shift the float upwards with 2. (Shifting it with 1 would be risky as the range is 0..1 and then it wouldn't know the difference between an actual 1 and a 0 that had been shifted.)
This means that theoretically creatures could move around between exits with no path finding at all, just by following the dijsktra maps. In practice there are other things playing a role as well, such as the Obstacle Tracker, so most of the more intelligent creatures will still need to do actual path finding. For small, stupid, swarming creatures it could definitely be used though, enabling what looks like intelligent behavior with pretty much 0 strain on the processor.
What most creatures will be able to use the maps for, however, is having a better general understanding about where they (and stuff they interact with) are in space. Which exit am I closest to? Which exit am I closer to than any other creature? Considering a group of creatures, towards which exit do they gravitate?
I have this one idea though, let me share it with you and tell me what you think. The idea is that the dijkstra maps could be used as beacons for triangulation of distances between
arbitrary points on the level. What I'm talking about here is not distance as in straight distance, which is easy, but actual pathing distance with the terrain counted in. If you are close to another place in coordinates but it takes a huge detour to get there, that detour distance is pretty much the only thing that's relevant, right? I'm thinking about this especially in terms of being afraid of other creatures, when fleeing it is very relevant information how close the threat actually is in terms of time to get to you, rather than mathematical shortest distance.
I think the triangulation technique could create pretty decent estimations for these non-direct distances. To get the exact distance you'd need pathing, but this technique is probably at least 10 000 times quicker in most cases, and will hopefully produce acceptable results.
Ok, so take a look at this. Here's a dijkstra map for each exit, and I'm trying to triangulate the distance between A and B. The data I have access to is the distance between those points and each exit.
So what I'd do here is basically imagine each map as a dimension. For the first dimension, then, A is at 25 and B is at 12. That makes our delta in that dimension 13.
ABS(25 - 12) = 13
ABS(18 - 60) = 42
ABS(40 - 6) = 34
(No I didn't count tiles, the numbers are just invented)
These distances in "triangulation space" can tell us some stuff. If we only have one dimension, we can't know very much, because there are many tiles on the map that are exactly 12 tiles away from a specific exit, and they are not necessarily close to
each other. E.g 12 tiles to the left of the exit and 12 tiles to the right of the exit. If we have more dimensions to play with though, I think the triangulation would quickly become more reliable. At three dijkstra maps my estimation is that it would be extremely uncommon for two tiles to have the same combination of distances to all exits, making the coordinates in "triangulation space" pretty reliable in their relationships to other coordinates. Correct me if I'm wrong here!
The system could potentially give a "false close", but never a "false far". An example of a "false close" would be if you have a room with an obstacle in the middle and an exit at the north and the south of the obstacle. A point to the west of the obstacle could have the same distance to both exits as a point to the east of the obstacle, making them appear identical or close in "triangulation space". An asymmetric placement of the exits, or a third exit, would help with that though.
A "false far" can never happen, because if the points are separated in
any of the "triangulation space" dimensions, they are
at least as separated in actual travel tiles as well. Look at A and B in the third picture above - the absolutely closest they could be while having the distances 40 and 6 would be if B was 6 tiles up on the same path as A, and then they'd still be 34 tiles separated.
Another way to say this is that if the deltas in all "triangulation dimensions" is 0, A and B might or might not be on the same tile, but if
any dimension has a delta larger than zero, A and B are sure to not be on the same tile.
The fact that the system might give a "false close" but never a "false far" probably means that of the three deltas calculated in the example above, you should pick the biggest one, and conclude that the actual distance can be no larger than that.
I think this makes it fitting for fleeing behavior. These distances could be used to evaluate how nervous a creature should be about another creature, and whether it's time to calm down and stop the fleeing behavior. "False close" isn't too bad in this scenario, because better safe than sorry, right?
Also it will be cool to check out how this can be used in swarming behaviors. Maybe you could even create some strange kind of dynamic path finding using it, if you move towards whichever neighboring tile is the closest to your goal in triangulation space rather than in actual space.
Oh, when I read through my post before hitting the button I had a small epiphany! One way to further eliminate "false close" could be to add the mathematical straight distance between A and B and treat it exactly like one of the triangulation dimensions! It has the exact same properties - ie that A and B can't be
closer than that, so it would work really well as a last reality check, eliminating for example the "obstacle in the middle and symmetrical exits on each side" problem. Shortcuts messes this up a little bit as they make it possible for tiles to be "closer than they actually are", so maybe it shouldn't be relied upon too much. But shortcut travel still takes some time, so it could be counted in to some degree...