JLJac on July 04, 2014, 07:17:10 AM:

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!

JLJac on July 07, 2014, 07:06:15 AM:

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.

JLJac on July 08, 2014, 01:07:10 PM:

@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?

JLJac on July 09, 2014, 10:27:24 AM:

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!

JLJac on July 10, 2014, 11:08:19 AM:

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 on July 11, 2014, 07:49:25 AM:

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!

jamesprimate on July 12, 2014, 06:26:38 AM:

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!

JLJac on July 14, 2014, 08:10:52 AM:

Wow that's really awesome! Ghost cats :D

Yeah, as James said, right now we're concentrating on making it before porting it, so it might be a while :S

Update 271
Alright, moving between multiple loaded rooms done!



In the gif, when you see the tiles up above the pit turn blue, that's me setting a destination. The lizard (pink cubes) has to make its way up there! Then the gif shows it as it's moving through multiple rooms in order to reach the destination.

Let's take a closer look at what's happening when you enter a room:



Notice how there's a path that's already there, and then it starts to swell out all over in two waves? When entering a room, the quickPathFinder - of a couple of pages ago fame - kicks in. It looks at all the neighboring rooms, checks which has the lowest pathing value (closest to the target) and makes a quick and dirty path to the corresponding exit.

The thing with quick paths is that they're made to be quick to calculate, not necessarily the most effective way to get there. Though they might be, if the maze is very simple. Anyhow, the quick path algorithm finds a quick and dirty way to the next exit, because the lizard should have something to follow right away when it enters the room. As it goes the real path finder will catch up with it, and it'll get a more reliable path, but the quick path is good enough to follow for the first couple of tiles.

As you might have noticed the accessibility mapping swells out from the quick path. This is because these tiles are already set to accessible when the level starts, and need to continue to be so as the accessible area is mapped, or the creature might stop in its tracks. Because of that I've fed all of the quick path tiles into the accessibility mapper as starting tiles.

Once the two layers of accessibility (reachable/possible to get back from) have been mapped, the path finder is told to create a new pathing generation, just like it would when chasing a target inside the room. But this time, it's the off-screen goal that's assigned. The path finding algorithm will search throughout the network of abstract rooms, and find its way to the current, realized room, where it will start flooding the tiles from the correct exit. In the gif this can be seen as purple, if you look closely.

Once the creature starts to follow this path, it stops calculating and just goes along - until reaching the next room, when the procedure is repeated.

One thing that was difficult in this was that when the creature is leaving the room where it's destination is, the destination needs to be translated from "tile space" to "abstract node world-map space". I solved this by partly using the quick connectivity check I threw together a couple of days ago, partly just checking straight distances to doors. It has been working OK, but the connectivity check is super expensive, so I'm thinking about more optimal solutions. No noticeable hickup though, so it might work just fine.

JLJac on July 15, 2014, 10:59:17 AM:

Yep, that's true. The thought crossed me that each segment of a corridor could be made to one big, rectangular cell, or similar solutions. In the end I decided to keep to this solution as the connections between different tiles are on the tile level, and because the path finder is not only supposed to be able to find a legal path to a legal position, but also the closest you can get to an illegal position. If you were to only map the corners, or some similar solution, it would be kind of unclear how mapping illegal space should tie into that, which is why I've kept it simple. But if performance issues start to pop up, I'll definitely reconsider it!

Update 272
Sorry guys, this is not gonna be an exciting one.

Averted a number of null reference exceptions that would happen because some coordinates were not properly migrated from tile space to node space on exiting a room.

Changed it so that instead of connecting a tile of the realized room to a node in the next room through an exit, the tile is connected to the node in the same room, which is then in turn connected to the next room. Ie it doesn't bypass nodes in the realized room any more, which is cool for a number of reasons, one of which is that it'll help later when I come to giving creatures cozy little holes to crawl down and hibernate in.

Moved the quick connectivity mapper to a static class, making it accessible from everywhere.

When deciding which exit a coordinate is closest to, in order to convert it to node space, I check both if it's possible to get from the coordinate to the exit and vice versa, hopefully giving a slightly better representation of tile coordinates in node space.

Etc etc etc.

Basically I've been cleaning stuff up. I tend towards working like that - first I just go in there and massacre the problems in whatever way possible, then I go over the solution and tidy it up. By now I think the path finding is actually solid enough to start moving on to either embryonic AI (keeping track of where I want to go, having a few modes of behavior to finite-state-machine between) or abstract creatures (creatures in a super-simplified state as they are outside of the currently loaded world), perhaps both. Abstract creatures also need some AI, such as a basic idea about "where am I going?" and "what am I doing?" to be able to know if the current behavior is "hunting" or "retreating to hole because of approaching rain". For this reason it might actually make the most sense to have these two next problems be one, and integrate the most basic aspects of AI with the super simplified creature.

jamesprimate on July 16, 2014, 05:23:51 AM:

did an update for the kickstarter crowd focused on pathfinding: https://www.kickstarter.com/projects/rain-world/project-rain-world/posts/914855

if you've been reading the devlog it'll be nothing new to you (im totally just paraphrasing what Joar has done the past few pages), but I tried to make it relatable to an audience that might not be as knowledgeable on the subject as you dudes. 

JLJac on July 16, 2014, 12:01:47 PM:

Update 273
Ok, so on to the next task! Today I've created a class for abstracted creatures, and made them able to move around between rooms. They're also contained in little lists in the abstract rooms, and receive updates.

Each abstract room has one "node" per exit. Abstract creatures keep track of which such node they are "in". The quotation marks on that last one is the complicated bit. A node doesn't really symbolize a specific area of the room, rather all the nodes tend to share most of the area of a level. Take a look at this room:



This room has three exits, and therefor three nodes. Let's call the top left one A, the upper right one B, and the one down in the pit C.

So, from A you can get to B, from B you can get to A, and every tile you can get to from A you can also get to from B. So it's not as simple as saying that a certain group of tiles represent a certain node. Rather nodes symbolize goals and destinations.

Now imagine that this room is offloaded, and represented solely with its nodes.

Remember how I told you that the game has mapped how to get from every exit to every exit for every room as every creature? That info is used here. Say that a creature enters from the left exit. It's position will now be set to this room, and node A. Each creature has a timer for how long it has been in that node. When it moves the timer is reset.

The creature also know where it wants to go next, in this case let's say out the exit C. The pre-baked mapping knows the distance between the two exits, so in the abstracted space it's very simple - once the creature has been in node A for a time that is long enough to correspond to that distance times a movement speed, it switches to node C. Then the timer resets, and the same procedure repeats for the next destination. This way the creatures move between nodes with a speed that corresponds to the actual tile-level distances between them.

The roaming behavior I have currently set up looks at what node a creature is in, and looks at exits for adjacent rooms. It can only go to nodes that are mapped as reachable, and also only follows paths that can be followed back, in order to not get stuck in a dead end. So say that the creature is in node A, then its next move can either be to move back out through the exit A, or the exit B, but not C as it won't choose routes where it can't get back. If it is in node C, its only option is to return out through the same exit.

The framework also allows for saving paths, meaning that creatures can have more deliberate movements throughout the world as well. An obvious example of this would be getting back to their dens when the rain gets closer. I imagine that it would be kind of cool to suddenly notice a lot of traffic of creatures through your room as they are all scurrying back to their respective dens.

In the future, if you were to walk into the room while the creature is moving from A to B, it'll just use the timer to place the creature at a certain point along the path between the two exits. That way you'll be able to walk in on a creature in the middle of traversing a room.

What I'm working with now, is having the creatures transition seamlessly between abstracted and realized modes. Say that you are in a room, hidden. Then you should be able to see a lizard come in through one exit, pass through the room without noticing you, and continue out the other. This means that the lizard has to change from abstracted to realized back to abstracted again, with some parameters remaining intact. More on this tomorrow!

JLJac on July 17, 2014, 07:55:39 AM:

Update 274
So now I have the basics down for the abstract creature framework, and am trying to connect it all together, so that creatures can move seamlessly between the two states of abstraction. However it also means that I have to re-structure quite a lot of the stuff handling things such as how rooms are loaded and the like.

I'm actually building some very fundamental infrastructure for the game here, so it takes a little thinking. Right now my basic idea looks like this:



Each of the areas is a level of abstraction. The very core of a creature is the top left cell, to which the other components are attached according to the nature of that creature and the level of abstraction.

An example of how a command might move through this infrastructure is when a creature with an AI addon (the player for example doesn't have an AI, meaning that the entire right column is absent) is given a new destination. This is handled from the top level - the abstract AI, and then the command is passed down to the AI and the path finder in turn. Processes in the AI are going to change the destination a lot, but each time the new destination will walk down this entire hierarchy - that way, when the room is suddenly abstracted and everything on the realized level is thrown out, the destination will still have survived in the abstract AI, which remains.

JLJac on July 18, 2014, 07:49:44 AM:

Thank you :D

Update 275
Similarly to how the human brain has its inner part, the reptile brain, and the surrounding cortex, the idea is that the rain world creatures will also have two levels of intelligence where the more complex works as an addon to the constant more static part. In rain world it's not going to be human level and reptile level though, rather like... Reptile and aemoba... Anyhow, the idea is that in the simple, abstracted world the creatures will make simple, abstracted decisions. When the environment is realized at tile level, the AI should get a more powerful component as well, to match it.

Today I've been having a bit of a conundrum. Here are the options I'm choosing between:

A - reptile brain keeps control always, and when the reptile brain decides on something ("let's hunt!") that command is passed down to the complex brain, which refines it into more complex behavior ("i'll go to this and that particular tile, etc etc"). This is cool because it makes the creatures behave generally the same regardless of if they're abstracted or realized, which gives them truer autonomy.

B - reptile brain controls the creature when abstracted, but when the creature is realized the complex brain takes the wheel completely. It still uses the simple brain for storing destinations etc, meaning that if the creature is suddenly abstracted those essentials will remain for simple brain to use, but while the complex brain is running the simple brain is not allowed to execute any behavior. This is cool because it's cleaner - two different solutions instead of one gooed together, and because it means that the complex brain isn't held back by the simple one as it can do its own thing without relating to the abstract behaviors.

Hmmmmm... I'm really unsure about this one actually! Which one seems the cleanest and easiest to work with to you guys?

jamesprimate on July 19, 2014, 01:35:52 PM:

Joar is going in deep with the Plato / Heidegger stuff!

Is there any advantage you can see from either of these over the other one in terms of easy of execution or processor strain? I like A simply because it sounds cooler, and i dont think keeping abstracted "personality" is such an issue (as the player will be unaware of it either way.)

jamesprimate on July 20, 2014, 08:51:04 AM:

i think its going to be $900.00 retail

JLJac on July 21, 2014, 04:35:08 AM:

A you say... Hm - in that case I'll have to do a little bit of thinking. I don't want the abstracted creature to be too heavy, as the very point of it is that hundreds of them should be able to run in the background as you play. But maybe there could exist a thing that goes over the abstracted creatures one by one and create "fake events" for them to react to - such as "hearing prey" which changes the mode from "idle" to "searching" for example. When the creature is actually loaded, this fake event engine would be replaced with the actual events of the room. Which would actually be a little bit of solution B I realize when writing this, but would perhaps hit the sweet spot between them. More on this later!

Today and probably tomorrow I'm making a website for our company, Videocult, which is necessary to get across some business hurdles. One of those is getting approved for the Bizspark project and receive a Visual Studio license, so that's going to be a nice boon for the development process. But until then, there might not be real devlog updates - so see you guys in a day or two!

JLJac on July 21, 2014, 01:44:30 PM:

Do you feel like sharing any of the ideas you had buzzing around your head?

jamesprimate on July 22, 2014, 06:14:07 PM:

uh guys, i think he meant "ideas about how to implement abstracted creature behaviour" hahah

jamesprimate on July 22, 2014, 07:55:35 PM:

ITS OK WE LOVE YOU GUYS <3

JLJac on July 23, 2014, 05:30:28 AM:

Website! I guess we are an actual game company now!

www.videocultmedia.com