next »

[Slader16]

Gosh, that looks crazy to program 


btw, I thought that you guys would find this interesting: http://blogs.msdn.com/b/somasegar/archive/2014/07/02/microsoft-acquires-syntaxtree-creator-of-unityvs-plugin-for-visual-studio.aspx

[JLJac]

Oh, look at that! Don't think it'll make a huge difference to us though... or maybe it will, because UnityVS doesn't work with trial versions of Visual Studio, and maybe now it will. We'll see!

Update 265
Off screen path finding. I'd say I'm about halfway through by now - the accessibility mapping shown above is for example able to map off screen abstracted levels, and the path finder is actually able to go through them as well, but there are some quirks.

The main hurdle here was that on the realized map, every AI entity will share an AI map, but in the abstracted world they will each have their own. This is because the movements in an off screen room is pre-calculated for each species, meaning that you will get a different looking graph connectivity in those areas depending on what creature you are. This meant that those two maps, for the local, realized room and for the abstract world, had to be connected at the room exits. As this connection was between a shared map and a private, there was some trouble, but now it actually seems to be working.

Still some stuff to take into consideration though. For example it doesn't yet consider the pre-baked connectivity maps of abstracted rooms, it just assumes that any exit in a room is accessible from any other exit. But we are really close to having a path finding system that's universal and able to seamlessly find paths in a room as well as between rooms.

Then again, following those paths is going to be another thing entirely haha!

[SolarLune]

Thanks for the technical write-up. I feel like I can imitate that method if I need some path-finding AI. Nice work, as usual!

[JLJac]

Happy to hear that! If you want to ask more in-depth questions, feel free!

Update 266
Now we have inter-room pathing! It actually seems to work! How it works, simplified, summarized:

1. On loading, a function called a "connectivity mapper" goes over all the rooms. It pretends to be each type of creature in turn, and using that creature's moves tries to get from every door in the room to every other. If it succeeds, it saves how long and difficult that path was (In room 3, as a Lizard, walking from door 2 to door 3, the path length is 21 tiles and the cost of the path is 321). If the path is impossible to traverse, it saves it as -1.

2. As a path finding creature is created, it creates a map of path finding cells for each tile of the room its in. It also creates a cell for each exit in each room in the entire game world. This might sound like a lot, but keep in mind that a 10*10 block of tiles holds no less than 400 pathing cells, so all of those exits in the offloaded world are going to be small fry in comparison to the currently occupied room.

3. The creature creates a network between these cells. For inter-room connections it's easy, if the room has 2 exits of which 1 leads to another room A and 2 to another room B, the first cell in the room (representing the first exit) should be hooked up to room A. Actually to the cell in room A that represents the exit towards the first room, but I said I'd keep it simple, haha. For connections between cells within the same room, it uses the connectivity maps mentioned before. This way the path finder will be able to know how difficult it's going to be to traverse a room, but the lengthy calculation is reduced to just a single integer number.

4. Run the path finding algorithm. The local grid of the currently occupied level is hooked up to the global grid through the room exits. The path finding algorithm is able to treat cells within the room and cells in the abstracted world equally, making it find paths seamlessly throughout the room as well as the world.



Finding a way from the bottom of a pit to the platform above, using off-screen rooms. Note that the path finding works from goal to start. The little free-floating cells on the left represent the abstract off-screen world.

I was once even pleasantly surprised by this when trying it out. I had a room that consisted of two little cells with no connection to each other, but just a connection to the outside world each. The offscreen pathing was able to create a path from one of them to the other through the offscreen levels, but not the other way around. I thought I had found a bug. In fact, one of the rooms that needed to be traversed in order to get between the cells contained a pitfall - dropping down was possible, but not getting back up. I found it fascinating how the very specific architectural traits of a level that to the game didn't even exist (it had never been loaded in that game session) could have a visible effect in this other room. It really made the world feel like a connected whole!


And, as a bonus, a little bit of path finding madness. The lizard isn't able to do its "flip over" move that enables it to turn around on a flat floor yet, so instead it proceeds all the way around.

[Nilanjan]

@Joar Amount of work you've put into pathfinding is amazing...Folks can learn a lot about pathfinding and the thought process behind it by just following this blog...Are you a self taught programmer?Just curious...cause if you're then I can have my hopes high
Great work..

[Wlad]

@JLJac I just want to tell you that I really appreciate these updates, your game is very interesting. I wonder how many hours daily you spend working on it?

[JLJac]

@nilanjan, thanks! Yeah, surely a lot of pathfinding in this game hahahaha! Still haven't turned out to the nightmare I expected though, so that's something we're happy about Yeah, I guess it would be accurate to say that I'm self-taught, not because people didn't help me, but because I never went to programming school. I've taken one or two courses that involved programming though. In the end I think the difference isn't very big - in the end the bulk of the learning is about just sitting down and learning it by yourself, and then it doesn't do a huge difference if you're going to be graded on it later or not!

@wlad, thanks! Appreciate it! I wonder too haha... Some days, way too many hours, some days too few - I'd guess it averages out around 8 hours a day.

Update 267
Today was one of the days it averaged on slightly fewer though, but I got some cool stuff done. Now we have a basic system for inheritance between creature templates, which will come in handy when it comes to, for example, the lizard breeds. If a creature template is created and passed an ancestor, it'll use the traits of that one as a base which will be modified by its own input parameters. So if I want to create a creature that's exactly like another creature, with only one difference, I can just tell it to inherit its trait and pass that one trait in the traits list to be changed. Good times!

Also creatures will can be tagged as not applicable for pre-baked pathing. This is because some creatures may have almost the exact pathing preferences (pink lizards and red lizards for example) in which case it's a waste to pre-calculate specific paths for them. The jury is still out on this one though, because it's just a few characters of data in each level file for each creature, and maybe the charm of actually having them all calculate their own paths might be worth it?

[GrahamOfLegend]

I don't even think "impressed" is the right word to use for this game. The amount of detail you put into the AI... Fantastic.

[Nico May]

I really hope that someday, once you finish rainworld, you consolidate all the pathfinding information both from this thread and what you haven't detailed into one, long, technical article explaining it all, because I have to say, from what I have seen/read, its brilliant, and I for one, would read the whole article through:D

[GrahamOfLegend]

I really hope that someday, once you finish rainworld, you consolidate all the pathfinding information both from this thread and what you haven't detailed into one, long, technical article explaining it all, because I have to say, from what I have seen/read, its brilliant, and I for one, would read the whole article through:D

I sincerely second this!

[JLJac]

Hahaha yeah most definitely! If there's anything I love more than programming path finding algorithms, that has got to be writing about programming path finding algorithms 

And on that note -

Update 268
Yo dawg, today I put a smaller path finding algorithm in my path finding algorithm... to... Let me explain!

The basis of the rain world path finding method is that as one path is being followed, the next is being calculated. This means that the paths are calculated not within a single frame, but over the course of several, and that the creatures are able to follow moving targets. How it works is pretty simple; the path finding algorithm works its way out from the goal as a flood fill. When it reaches the creature, the creature starts following the path. Once the creature is following the path, a path to the next goal position (wherever the goal has now moved to) will start to be calculated. It's assumed that the new goal will be somewhat close to the last goal, so the creature will continue to follow the last path as the new is being calculated. The creature will never follow a perfectly updated path, but it will have a reasonably recent one to go by, and it is quite a lot easier on the processor as an entire new path doesn't need to be calculated every time the goal moves.

I think of this as a path finding algorithm that's optimized for having several creatures chasing moving targets. Contrary to an RTS rain world will have almost only moving targets.

Ok, with this in mind, take a look at this. Notice how each time a path connects with the creature, the next one is started?



This is done pretty simply. Each time the mouse is assigned as destination, but it's actually saved as a "nextDestination" variable. When the creature is following the most recent path or the path has exhausted all its options and knows its unable to reach the creature a new path will be initiated, with nextDestination as destination. You following? In the gif above we see a lot of the former and none of the latter.

So, there's a problem with this system. Say that the creature is in a small enclosed room. The path finder is told to find its way to a position somewhere out in the big world outside the room. A new path will be initiated, and the path finder will chug away at the vast sea of tiles in the world, without finding a way into the room.

Now the AI changes its mind, and the path finding goal is put inside the small room again. Notice the problem? No new path will be initiated inside the room, because the creature isn't following the most recent path, which is still searching all over the world for a way to get to the creature, and the path won't have exhausted every option in a loooong while, as it has to look at every tile in the world first.

So, the solution is to just assign a new path every time the goal moves, right? Nah, that won't work. If the goal moves, as it will when following a creature, there will be a new path each frame, and none of them will have time to reach the pathing creature.

This is where the path finder in the path finder comes into play. It's a super quick little path finder that maps whether one place is close and reachable from another place. So, when assigning a new destination, I check if this new destination is close to the old destination. If so, I simply do as first described, save it as nextDestination. If it is not, however, I scrap the old path and start a new one. The old one probably wasn't going to help either way.

So, in the scenario, this would mean that as the goal is moved into the small room again, it's quickly determined that this area is enclosed from the last destination - and the last path will be discarded and leave way for a new one, inside the small room. The creature will appear as more alert, as it will adapt to the new situation quicker than if it would've had to search the entire world for a path to a place it didn't even want to go anymore first.

Whew. Told you path finding was gonna get crazy!

In other news, I've enabled lizards to enter short cuts, and brought some of the path finding stuff together and had it work simultaneously. So, now we for example have the "pathing through places I know I can't actually go" stuff working simultaneously with all the other stuff, etc. The different elements tend to not get along very well at first when put together, but I think I've made it work. Have some ideas for re-structuring stuff though... we'll see.

Also been developing some ideas about how off screen creatures moving about are going to work. Off screen creatures are probably going to be a little... schrödinger's lizards, in that they'll be in sort of undefined states until they need to be realized... It's going to be interesting!

[dancing_dead]

I hope you leave the option to view pathfinding visualizations in the final game, some of it looks almost tasty, so pretty you do your debugging!

[Slader16]

How do you go about actually drawing the pathfinding routes?

[JLJac]

Hehehe thanks! It's just an object that's hooked up to a path finder on initiation, and every time the path finder does something it checks if it has a draw object, and if so, throws a command at it. Not going in the game though, sorry!

Update 269
Today I've been doing things too petty to really be worth a mentioning - which is a good thing, because it might mean that I'm actually starting to wrap this thing up. Petty things include:

- In corners the lizard would believe that a path was accessable, and for one tick follow it, leading to the path being abandoned because it was "already complete and being followed". Took some very intense staring at a weird little squiggle in my note book until I figured that one out. If I ever did, but the bug went away.

- Right from the start when a new goal is being designated, it checks if that tile is reachable. If not, a "looking for the closest possible I can get to this point that I know I can't actually reach" bool is set to true, and the path finder follows slightly different rules. For example, if it knows that it will be able to reach the destination, it doesn't even check tiles that are not marked as reachable - they're just a waste of time and memory.

- When setting a new destination, it checks that this isn't already the Destination or NextDestination, and thus saves expensive connectivity checks.

On a slightly more interesting note, I've done some actual behavior - though I'm probably going to redo it once I get around to giving the lizards unique personalities.

Look at this scenario:



Where the mouse is (red little square), the lizard wants to go. But I've disabled shortcuts here, so it's unable to get to the upper part of the level. Instead it should get as close as possible, as mentioned in the note above.

Now, depending on how I weight the "which tile to check next" heuristic, we get different results. In one version we always prefer checking tiles that are legal to move in first. In that case the whole connected above area will be filled in first, and then start to swell out pretty evenly in all directions. In this case, the blob will first make contact with the lower connected area in the place I've marked with blue, and then spread across the floor. This means that the lizard will follow the path to where the blue area is, and then hang out there as that's to be considered "the closest I can get".

Another way to do it is to weigh in proximity to the original goal more. Then the blob of checked tiles will spread pretty evenly outwards from the goal until it hits a mass of legal tiles - then it will spread inside that mass quickly until it catches the lizard. In such a scenario the lizard will go to the red zone and hang out, considering that "the closest I'll get".

Maybe to you the red area seems more correct, as it's closer, simply. To me too, which is why you see the lizard hanging out there. But you have to have some of the logic that leads to the blue area as well in there if the creatures are to appear intelligent. Imagine a platform that has only one way to get to it; passing through a narrow corridor and then doing a jump. If a creature that is not able to do that jump is supposed to get as close to the platform as possible, you wouldn't want it to just hang out on the floor underneath it. That would be worthless if it were to for example guard some prey that has escaped to the platform and isn't supposed to get away from  there. Instead you'd want it to hang out in the corridor before the jump. That way it's perhaps not the closest to somewhere on the platform, but it's the closest to where you get to there.

This is the blue-zone behavior. If you look at the blue zone in the picture, you notice that this is the place that where if you were able to climb or fly only a few tiles you'd have access to the entire top part of the level.

So, now the path finder has these behaviors in it, and balancing between them is as easy as setting a slider between 0 and 1. So maybe different creatures will have a slightly different approach to this, some might tend more towards the one and others towards the other.

Note that this is just path finding, not AI. The AI will do all the actual thinking and just pass a simple "this is where I want to go" coordinate to the path finder. When AI is up and running, and a prey is climbing around in the unreachable top part of the level, the AI will calculate where the creature would fall if it were to fall, and try to hang out close to that place on the ground below it. So, neither blue zone or red zone. But that's a later issue, hehe!

[JLJac]

Update 270
Woho! The path finding seems to be more or less at the point where I'll be able to get it as a general creature-nonspecific behavior. I will of course revisit it when I get into doing individual creature behaviors, but the general principle seems to be working!

With this victory, I moved on to creature-nonspecific path following issues. First up, making a creature follow a path through multiple realized rooms. The issue - a creature only has a tile-level resolution map of the room it's currently in, for the others it uses the abstract node system. This means that when moving from one room to another, it needs to discard an entire path finding map for that room and create a new one for the room it has entered.

Furthermore, when entering the room it can't just lose its orientation entirely. If its destination is a specific tile within that room, it needs to make a quick path to that tile. If the goal is in fact another room, and it's just passing through the current one, it needs to look at all the exits except the one it came from, and for the exit that has the lowest pathing resistance (closest to the target) it needs to create a quick path and fill in the cells in order to get there.

This last issue is what I'm working with now. It's wonky and tends to give paths to random internal shortcut entrances instead, when it doesn't just crash the game. But it still feels good to be working with the ability to follow paths, not calculating them. Progress is being made!

[dasdsad]

I would play this game purely just to be able to move around with that splendid animation work.

This is some incredible stuff. 

[Rojom]

I am so impressed by the frequency and thoroughness of these dev updates.  Been following you guys since Adult Swim picked you up and you announced Rain World was coming to Vita. I know this may be a premature question, what with all of the focus on AI and path finding, but have you guys begun work on the Vita version?

Also, are you planning on having predators beyond the lizards? I just can't get enough of this world you've created, and the idea of other beasts hunting  me too sounds scarily awesome. Those garbage snakes I could picture being stationary hostile creatures as well.

[jamesprimate]

Haha yeah were a bit far from talk of porting it. That's like waaaaay down the line once its nearing completion. Though it is  the sort of thing that is important to take into consideration during development so you don't run into compatibility problems down the line. But don't worry, we're keeping it in mind!

[Rojom]

Alright, thanks for the reply. It's a pleasure to watch this game grow, so I'm happy to wait until it's ready.

[eigenbom]

I saw this illustration and thought of you guys (link).