Page 2 of 5

Posted: Mon Sep 02, 2013 1:50 pm
by henke37
I think that the idea is that the map can be split into predeterminated larger chunks. Like say, on a by room level. The best path between the rooms can then be precomputed and stored. This makes further path finding relatively trivial.

Posted: Mon Sep 02, 2013 7:45 pm
by JSwigart
Flow fields are basically just a precalculated and stored path search usually with respect to a specific feature of the map(nearest supply region, nearest infirmary, etc). Similar to ... _algorithm where you calculate a 2d lookup table so that you index it by the start node and the destination node to find the next node to travel to. As you mentioned, the strength lies in providing virtually free pathfinding such that swarms can easily move around with little cost. Their weakness is that the 'continuum' as you mention is essentially limited by the number of layers you maintain, which has a memory cost per layer. Many demonstrations of a flow field have huge swarms of units swarming to a single specific destination. This is because the flow field is calculated with respect to a given destination, or destination type. This produces a layer where the units need only follow the weighting ramp to the destination. Even this simple example has plenty of use cases in this game. Each are represented by a maintained weight grid, and the AI that need to move around would do so with respect to whatever its current destination is. The memory usage and updating the layers is the bulk of the cost, but memory in an even average PC these days is huge compared to even a worst case cost of storing these layers, and updating each layer can be done in separate threads. Many layers would very rarely change, others would change pretty often as the player builds, but these updates are not computationally expensive. They are just tile map flood fills most of them, or a dijikstra search. Generally it is easiest to update the layers with respect to the goal tiles. For the 'nearest shower' layer, you first initialize all shower tiles with 0, and then flood fill out, increasing the cost with each expansion. When you are done, any tile that has an 'invalid cost' means there is no path to the shower, any tile with a valid cost need only follow the neighbor with the lowest value in order to travel towards a shower. Not only is the small tile map nature of this game ideal for this, but most of the game mechanics are good fits for representation this way.

- Proximity to shower - always use the nearest shower
- Proximity to food - always use the nearest canteen
- Proximity to freedom - escape tunnels
- Proximity to delivery - choose the guys with the fastest access to pick stuff up for delivery, have kitchen supplies delivered to the closest supply area to the kitchen
- Proximity to yard - always use the nearest yard
- Proximity to recreational object
- Proximity to visitation center
- Proximity to 'indicent' - this layer could be generated on the fly based on specific problematic prisoners, repairable objects, etc. Guards can then be trivially allocated, based on who is best able to quickly respond, to those indicents, or repairmen, etc
- Water pressure

Since the AI normally have locomotion motivated by reaching a discreet type of area, they need only use the appropriate layer to reach them very cheaply. It could also make cascading behaviors easier to implement. Maybe prisoners will favor the nearest reachable visitation center, which translates into the family needing to go to the appropriate visitation center, and not simply the nearest to the place they are dropped off.

Sure this could all be done with A* searches at runtime, but it would be much cheaper to use these sort of maps, which would allow more AI to be used, larger maps, etc.

On the topic of memory usage, which is the weakness of this technique, in the context of this game isn't not even close to being a significant weakness given the smallish scope of the tile map. From a quick search, a 200*160 map is the 'large' map size currently. Just to use that as an example, in an unpacked layer representation where you allocate 200*160*1 byte, where the byte is only 1 of 5 values(none left, right, bottom, top), a layer is 31.25 Kb. Which is trivial in the memory capacities of even handhelds these days. This is even bloated, as we are only needing to store at most 5 values, so a full 8 bit type is overkill. If one were really picky about the memory usage you could pack the layers into a 2d bit array and store 200*160*5 bits into 19.5312 Kb, which is a significant percentage saving, but probably not necessary unless the number of layers gets really high and you want to be extra conservatives on more limited platforms. In 1MB of RAM, you could store over 250 of the 31.25 Kb layers. Pretty trivial memory usage. Technically we can encode the information we need into 4 bits, but I won't go into that here. The CPU savings could then go toward supporting much larger maps, many more AI, etc. With a ton of layers, the cost of maintaining them would be the bigger problem, but still very managable compared to doing on demand pathfinding.

It's still basically A*, but the main difference is that you are storing the data set in precalculated layers with respect to a single context of information. Other layers could be the accumulation of multiple weightings. You end up having potentially many layers of flow field pathing for all the AI to simply index into like an array when moving around. If a guy needs to move to the nearest supply pad, you look at his current tile in the 'supply proximity' layer and moving to the destination becomes virtually free(in cpu terms). It's also easier to accommodate changes to topology. For example using just A*, you might need to do a bunch of additional bookkeeping to detect when you need to invalidate current paths when something new is built, or when a new path is opened up, if you want guys currently moving around to account for those changes. When these changes occur with the flow field, you update the flow field and everyone immediately takes into account the new information without their own personal book keeping being necessary, because in a flow field, units generally only look 1 step ahead to 'whats the next tile to move to from my current tile', they don't build a full path across the map that you worry about invalidating. It's very similar to saving the search state of a dijikstra search and re-using that flood effect of the search to avoid doing the search again later as long as the obstacle and weightings remain the same.

My primary area of professional AI development is shooter focused(Mercenaries 2, Doom 4). It is very difficult to get AI to make intelligent looking decisions if they are making decisions at an individual level. We found that we got much better results if we have a more tactical level of the AI that was analyzing the suitability of every ally with respect to every behavior, with respect to every enemy. I dubbed this a 'token manager', named after the common practice in fighting games where AI would circle the player and purposely 'take turns' attacking the player. Also often called the 'kung fu circle'. A token is a specific behavior for a specific attacker versus a specific target, and this sytem generated a global prioritized list of tokens that the AI would simply grab the highest priority token generated for them. For things like melee behaviors, that monsters tend to focus on a lot, the single most important component of the desirability to melee is the path distance to the enemy, so this system would batch up pathfinding in a flood fill kind of way so that it ultimately knows how close anyone is to everyone else, without needing to do an n^2 A* search. From these pathfinding results, the global prioritized token list was created, and with a more global context like this, it was able to intelligently allocate the melee token to the monster with the best proximity to the nearest target. It is tricky and expensive to do it otherwise. This allowed us to tweak the difficulty of encounters by changing the number of token 'slots' available on a particular target. If we wanted more melee pressure on the player, we could allow 2-3 melee token 'slots', and the system would automatically allocate the nearest 2-3 enemies(nearest in path distance), to the AI, and it could distinguish between the best enemies to attack the player, versus the best enemy to attack a sidekick AI.

It's tricky to understand the hidden complexities in target and behavior selection unless you have some experience with implementing it. In some games with only the player, it doesn't matter as much, but if you have the players plus a number of NPCs versus an enemy faction, it is very complex to get them to make decisions that don't look broken at some level. Many games go a different route and provide the AI with so much designer side hinting that they can craft the behavior a little better with hints. We used this system to try and be able to drop in enemies and allies anywhere and get good looking behavior. The global prioritization of these tokens also allowed better suited AI to interrupt a less suitable AI to take over a specific behavior.

That's all a long way of trying to explain that if you have these weighting maps that have built into them a variety of behavior contextual information, or even a single context of information(proximity to X), because it is map wide, it becomes easier to do a number of things.

To extend that system with how it might be useful in a game like this. If you have a weight map where each tile is distance to the delivery area, when things are dropped off, You can very easily allocate the capable units nearest to that delivery area to go and pick the items up, without pathfinding for any of them, because you already have a proximity to delivery area layer precalculated.

If those guys were doing something else at the time, that task would be in the prioritized token list as well, and if it were more important, or they were particularly suited to completing it, it may or may not be a better choice for them to change their task. That's the beauty of this sort of system, that it can make decisions easy that better take into account the current state of the entire map and other units. This sort of decision making is extremely difficult to do another way. If someone gets interrupted by a higher priority token/task, the old task would get allocated to the next best fit to accomplish it. The AI still needs the ability to reject tokens so that they can be allocated to the next best guy, so for example, if a guy has already picked up a particular item to install it at some location, he would reject any tokens that aren't 'install item x' tokens. This would solve the situation of a guard running across the prison to open a gate for someone when there was a nearer guy that could have done it, but didn't because he was doing something else.

As an AI programmer that loves to build these types of systems, it makes me envious to play games in which these systems would work very well, because I would love to do AI for such projects.

Posted: Mon Sep 02, 2013 8:51 pm
by Flint
I'm all for an update for performance enhancement. You really can't keep building on something that cant work beyond a certain point or else you will enviably hit a point where it all just falls apart and your left with a mess that's now 20x its size to fix. We want new AI, Stuff, Buildings, ect but if its all build onto a brocken engine that cant support it all then all your doing is decreasing what you could already do. Their should be a update focuses fully on AI updating, background processing correction and stabilization. Once that's all done then you can add more and if any errors pop up then they will be minor in comparison, easier to track down and correct.

Posted: Mon Sep 02, 2013 8:56 pm
by xander
Very interesting. Thank you for the clarification and expansion.


Posted: Mon Sep 02, 2013 10:24 pm
by LennyLeak
JSwigart wrote:...Wise words...

That sounds really cool and interesting, and props for explaining it so even a code-novice like myself could easily understand it. I hope the devs look into this, cause it sounds like a really clever approach.

Re: Improve performance?

Posted: Tue Sep 10, 2013 11:22 pm
by prototype
It was a great read.
I am not a coder myself but I have some experience with math.
Now I would like to start building a game or something just to try it :)
To bad that is a lot of work.

Re: Improve performance?

Posted: Wed Sep 11, 2013 3:24 am
by paktsardines
What I find particularly interesting is that it appears some form of flow fields is already being used by prisoners to find the best path for digging their way out of the prison. See this image. If so, perhaps it can be adapted to also handle regular prisoner pathfinding.

Re: Improve performance?

Posted: Wed Sep 11, 2013 11:35 am
by redd
I've found that dropping the sound sample rate down to 11KHz keeps things smooth. Although the game does intially sound a little rough after that, you get used to it.

Re: Improve performance?

Posted: Wed Sep 11, 2013 3:02 pm
by goodvibesman
Just about any computer is going to slow down after running such a CPU intense game for a while, people have the same problem with Dwarf Fortress when they reach about 200 dwarfs. There's just so much pathfinding going on at once, it's no wonder the game tends to slow down.

Re: Improve performance?

Posted: Wed Sep 11, 2013 4:46 pm
by yos233
One word, my friends, one word: Multithreading


Posted: Wed Sep 11, 2013 5:32 pm
by LeftyRighty
JSwigart wrote:Flow fields are basically just a precalculated and stored path search usually with respect to a specific feature of the map...

The alpha 13 blog vid demonstrates such a map for the tunnelling... so it looks like at least some of it follows this method. Not sure about the more "active" agents like guards though, given that high numbers of staff (skewed towards guards) starts to cause problems it might be that they are working on active search pathfinding and not a precalculated layer

Re: Improve performance?

Posted: Wed Sep 11, 2013 6:34 pm
by xander
yos233 wrote:One word, my friends, one word: Multithreading

While the game certainly has parallelizable bits and bobbles, that only helps so far. For instance, assuming that the multithreading library has zero overhead, the best performance increase that I could hope to see would be a factor of four (I have a four core machine). Parallel algorithms probably need to be implemented, but more efficient algorithms are just as important (if not more important).


Re: Improve performance?

Posted: Thu Sep 12, 2013 1:20 pm
by iScripters
Tweet by Introversion:
Our programming whizkid Johnny Knottenbelt today found a performance enhancement that doubled the fps of the game on some large maps

Re: Improve performance?

Posted: Sun Sep 15, 2013 6:50 pm
by Sjiep
An extra vote on this topic.

Performance mainly seems to become an issue when building stuff. Especially the sound starts to stutter like crazy (and as the result the whole games starts to 'slow down'.
I have now completed my prison on a small map with roughly 100 prisoners 'living' there. Since I've reached this point and am not building anymore the game seems to run fairly smooth, even over longer periods of time. However, when I was still (actively) building and improving certain areas of the prison, I had to save and restart the game every 20 minutes. Constructing new objects and switching to the utility screen seem to have a very bad influence on (sound) performance.

I know the game is still in alpha stage, and in that sense it is not a complaint. But more a form of feedback, in which in my opion the game could be improved performance wise.

Re: Improve performance?

Posted: Tue Sep 17, 2013 8:11 pm
by prototype
I have had the same experience.
Every time I start to build something the game starts to slow down.
When I keep it running while not changing anything it will do much better.

My guess is that the jobs the simulation creates for the workers/staff somehow are bugged.