Experimenting with pathfinding

[Daixiwen]

Hi everyone!

I wanted to experiment a bit with the pathfinding algorithm in the game, to try and understand how it works and how it can be used to design a prison with several independent blocks, or with independent prisoners and staff corridors.
So first I needed a prison with only one prisoner, to make it easier to experiment and see what happens. My first idea was to make a prison with only one cell, have a guard put a prisoner in there and then fire the guard. It turned out to be a bad idea, because when you fire all the guards, the prisoners just escape . So I hired a new guard and designed a second prison with a holding cell.
Here is my experimental one-prisoner prison:



And my paradise prison for all the others:

It isn't exactly a paradise (electricity and water is really overrated ) and almost all prisoners escaped on the first day. Having all 6 attempting to shower on a 1x1 space was probably kind of messy. The only one staying is injured and cuffed, it looks like those can't escape.

But I was now able to play a bit with my guinea pig.


The prisoner has a nice and comfy cell with everything he needs (except food) but I need to make him run a bit. A slight adjustment to his schedule will take care of that.



My first experiment was about those famous "staff only" doors. I can confirm one of the hypothesis on this forum: the prisoner will ignore the door type when determining the shortest path to his destination, and will just stupidly wait in front of the door that it opens. Someone else suggested that they would "memorize" a path and then always follow it, but this isn't true. I had him take the long route first, and then placed a staff door. He still wanted to take that new door and would only take the other route if I removed the door and put the wall back again.




My second experiment was to find out which of the showers the prisoner would choose if several were available. Would it be the closest one geographically, or the one with the shortest path? To check that I brought the shower closer to the cell, and put another shower over the cell. The new shower is farther away from the cell, but on a shorter path. It turns out he chose the new shower, the one with the shortest path.



In the mean time…



My third experiment was about the assigned cell. I made a new cell just next to the shower and wanted to see which one he would pick after his shower. It turns out he went all the way back to his first cell. So once you assigned a prisoner to a cell, he will always go back to this cell, not to the closest one.



Finally in my last experiments I wanted to see if it was possible to have several kitchens or canteens, as I saw in another thread it didn't work. And I'm afraid I have to agree...
I made another canteen/kitchen block and assigned a second cook to it. The cooks started to put supplies in their respective kitchen, but then moved both to the second one, and then both to the first one, until all the cookers were filled up. At the time of eating they grabbed the cooked food from both kitchens and put all of it on the serving table in the first canteen, the one on the right. The cooks just kept on switching from one kitchen from to the other. It seems to work at random, they take the food from a random fridge and put it on a random cooker. But the cooked food always end up in the first canteen. So it seems possible to have several kitchens (although the cooks will keep running from one kitchen to the other) but we can have only one canteen.



I also wanted to see which canteen the guinea pig would choose. His first meal is after a shower, and the canteen on the right is closer to his position at that time. The canteen on the left is closer to his cell. I thought he would always go to the canteen closest to his current position and I was right. He had his first meal after the shower in the canteen on the right, and his second meal (after a nap in his cell) in the canteen on the left (unfortunately for the poor guy, with an empty table). So prisoners don't have a determined shower or canteen, they just take the closest one (i.e. the one with the shortest path) when needed.



I tried to deassign the first canteen to see what happens. The cooks still put the food on the serving table in the unassigned canteen…. odd. I actually had to dismantle the serving table to ensure the cooks would start to use the other canteen.



So to summarize:

• prisoners always come back to their assigned cell, they don't switch
• when going to the showers or the canteen (and probably the yard too) they pick up the one that is on the shortest path from their current position (and not always the closest one!)
• when finding the shortest path, they ignore the door types. If one or several door on the shortest path is a staff only door, they will just wait in front of it until a staff member comes by and opens the door. Then they will walk through it. It makes it impossible to create staff only corridors or rooms if they are on the shortest path between two places a prisoner can use. -> BUG
• cooks can't be assigned to a specific kitchen, they will move randomly from one to the other. They will always put the food in the first canteen, whereas the prisoners pick up the canteen closest to them. So don't create several canteens. -> BUG
• if you need to move the canteen, make sure you dismantle the serving tables from the first one so that the cooks go to the new canteen.

[PerfectDeath]

You should play around with solitary rooms, I have a game where I had 16 prisoners awaiting solitary but no money to expand much, So I re purposed some cells to become either solitary rooms with a jail door or solitary rooms with a solitary door.

The door does not matter, in fact I don't even think you need a door for a solitary room...

Next I found that after their solitary term was over the guards usually didn't escort them out; the prisoner would walk out only on my order to reassign, I would reassign them to the holding room manually to get them out. Next I found guards putting non-solitary prisoners inside the solitary rooms, one even had two prisoners inside of it. @_@

Probably could test more with it, lock a cook or worker in a room with some prisoners to get solitary sentences.

[Legion303]

Thanks for all the experimentation--this answers several questions I had about the pathfinding and now I don't have to do the experiments on this build myself.

[a__gun]

Nice clear logical approach - good job

[Daixiwen]

Thanks! I wanted to see what was possible in order to design a prison with several independent wings. It looks like I'll have to put a common canteen somewhere in the middle of the prison, and can then place wings around it, and place the rooms to ensure that the closest shower/yard/common room is always in the same wing, to prevent prisoners from running from one wing to the other.
I will also probably have to enforce one hour of sleep after each meal, to force the prisoners to return to their wing before doing anything else. And after all it's better for digestion
The fact that they always look for the room with the shortest path and not the closest one geographically will also make this easier.

[stephenarcher0]

I have also found that injured prisoners will be escorted to hospital beds, even if I haven't assigned the room as a medical room.

[dsiOne]

You should play around with solitary rooms, I have a game where I had 16 prisoners awaiting solitary but no money to expand much, So I re purposed some cells to become either solitary rooms with a jail door or solitary rooms with a solitary door.

The door does not matter, in fact I don't even think you need a door for a solitary room...

Next I found that after their solitary term was over the guards usually didn't escort them out; the prisoner would walk out only on my order to reassign, I would reassign them to the holding room manually to get them out. Next I found guards putting non-solitary prisoners inside the solitary rooms, one even had two prisoners inside of it. @_@

Probably could test more with it, lock a cook or worker in a room with some prisoners to get solitary sentences.

My solitary 'rooms' are checkered along my 2-wide main jailblock path. Right now it's basically sit in the corner punishment, not sit in a room deprived of all external stimuli punishment.

[Bedders]

Looks like a great experiment Very detailed, and incredibly informative. Well done and thank you

[Harmonica]

This is the sort of thing I would do if I was as patient and thorough Good job. I expect however a lot of this will change (especially the stuff that needs fixing!), but yes, it's interesing.

The solitary cells generally mess things up. I think perhaps that jobs get queued up in memory somewhere, so that one prisoner can have a list of jobs associated with him assigned to a guard, which might get out of date for whatever reason (he gets beaten on the way back from canteen, and moved to hospital, etc). I've observed guards moving prisoners back and forwards between cells and so on seemingly for no purpose possibly because the jobs were still queued somewhere.

Might be wrong but that's what I observed.

Also: about the 'memorizing paths' thing. I mentioned that idea somewhere. I'm not sure exactly how your test worked but it seems to me that when given a shorter path to a location that path will then stick permanently, even if that path is no longer functional and even if there is a new shorter path. The paths don't (always?) get deleted, seems to happen if you've toggled doors because that doesn't register on their radar.

[Daixiwen]

I tried to reproduce that memorizing paths problem but couldn't. Each time I created a new shorter path my prisoner took it without delay.

Based on those findings I tried to create a prison with two independent wings (32 prisoners in each) and a shared kitchen/canteen. It is almost working as I planned it, but a few prisoners have a behaviour that is not consistent with the findings I wrote in this thread. I'll experiment more and post what I find, but I wonder if the pathfinding algorithm becomes a bit "lazy" when there are more and more NPCs in the prison...
My biggest problem now is the prisoners that wake up in the morning and want to go to the weirdest and most remote toilet they can find. I haven't found the logic in that yet.

Oh and something else... on my design the shortest path from the yard or the showers (and some rooms) and the kitchen goes through several staff only doors, on a path completely different than the one used by the other prisoners to go to the canteen. So it's very easy to create a trap for those that do contraband. They want to go to the kitchen instead of the canteen, and get trapped behind those doors . It's a bit like fishing. But I can confirm something others observed here: the prisoners that want to go to the kitchen for contraband respect the staff only doors, and get stuck behind them. The prisoners that want to grab a knife, on the other hand, just walk through the staff only doors as if they were regular doors. They don't even try to damage the door, they just walk through it.

[gsuberland]

Yeah, cell IDs are stored in the prisoner record in memory. They cell IDs also get temporarily transferred over to a guard if they're transporting a prisoner, so technically the guard has an assigned cell during that time. The fun part is that, if you hack the CarryID.i and CarryID.u values, you can make guards carry guards or builders carry prisoners. The game usually crashes when they get to the destination though.

One thing I haven't tried is nested carrying, where you chain CarryID entries over a few different actors, so you get a worker carrying a guard carrying a prisoner. Would be amusing!

[Guvnor]

Very helpful post Daix. I wish I would have taken a screen shot but I have seen so many prisoners crowded around the staff-only door to my kitchen that the regular staff couldn't get close enough to the door to trigger it to open so it created a deadlock. There were about 7 prisoners trying to get in and another two coming out. Three janitors couldn't get past the 7 prisoners so the situation just remained deadlocked until the next chow time.

[Daixiwen]

So I tested my two block prison a bit more. By forcing my prisoners to have a shower right after sleep, all the prisoners in the top block went to the top shower room, as expected. Among the 9 prisoners in the lower block, 4 went to the low shower, and 5 went into to the top building and to the top showers, which isn't logical. There seems to be something with the pathfinding with more prisoners...



As for the toilet problem, I still don't get what is happening. I thought maybe the AI moved some prisoners to the prison's first toilet, so I edited the save file and moved the first 3 toilets I placed (in a used-to-be holding cell) outside of the building. You can see them in the middle of the picture. All the prisoners ignored them. So it is something else...



I also removed from the save file all the prisoners in the top block but one and see if it works better then, but it's the same... from the bottom block, 4 prisoners showered inside and 5 went to the top building to shower.



I think I'll stop my investigations for now and wait for the next alpha, hopefully with a better pathfinding algorithm

In the mean time... one canteen, one kitchen, one yard, one common room and one shower room!

[Daixiwen]

I found it! The 5 ones that rushed to the top shower had a high need for hygiene, while the other 4 didn't.
I edited my savefile again and removed all the needs for hygiene, forced them to shower again, and voilà!!!




I don't know if we can generalize to other needs, but at least in the case of hygiene and showers, the pathfinding only works correctly when the prisoner doesn't actually need to shower. In that case he just goes to the shower room with the shortest path. When he actually needs to shower, it seems to be a different algorithm that is used, leading to a non optimal path. Looks like a bug...

[Daixiwen]

Sorry I'm replying to myself again, but I saw the same thing with Yard and Recreation. All the prisoners with a high need for recreation went to the top yard, whereas the others stayed in the correct one.