next »

[jamesprimate]

the "Joar is too busy hanging out on an island to bother with an update" mini-update 281.5

So island or no, we took some time and talked about AI archetypes and what to do. The next step of that is developing the AI's "tracker", which plots the expected position of a creature or object for the AI to follow when that creature or object is out of view. Basically, it creates a mental "ghost image" estimation of where it thinks that target will be via some criteria. For example: a lizard chases you around a corner and can no longer see you. Which direction does it take to continue to follow you? THAT'S the tracker. As you can imagine, this has big significance for hiding, sneaking and plotting, AKA a bunch of Rain World.

Joar had 2 options for this: a tile-based method and a physics-based method, each with certain advantages:

* Tile-based seems more robust in general but suffers from a lack of granular resolution (1/20th as accurate as physics method) and difficulty predicting more "physics-y" shapes like parabolas (such as the arc of a jumping slugcat!), that might occur.

* Physics-based method models parabolas and gravity well and also has has the advantage of being able to easily and more accurately model the velocity / vector of an object to "ghost image", but could potentially suffer from "in-between state" jitter and other weirdness.

So the decision was of course to do BOTH: Tile-based tracking for objects on the ground and then physics-based tracking kicks in for jumps (and perhaps flying behaviors.) And that's what he's up to right this moment!   

I'm getting assorted things prepared for PAX Prime, where we'll be showing the Rain World alpha again at the Adult Swim booth. Also, I don't talk about this too much in here, but the Rain World soundtrack is getting deeeeep: Well over 60 tracks written so far. Not all of those specific ones will be used of course, but the way things are mapped out now, 70-100 tracks might be where it ends up. Kickstarter backers could wind up with a nice 3-4 disc set. Quite a bargain! XD

[JLJac]

And now, straight from the island in the Swedish countryside!

Update 282
After talking a little with James, we have started to pin down the AI stuff some. Still I feel it might need some digestion, and have instead started on the next (and last) module that will be shared by almost all AI creatures - the Tracker.

The Tracker module is basically a piece of code that makes creatures be not omniscient. It creates ghosts for each other creature that the creature knows of, and acts as a combination of visual processing unit, memory and anticipation/prognosis intelligence.

As James described, the Tracker runs a ghost for each other creature. When the other creature is clearly visible, the ghost will be updated to its position each frame. When obscured, the ghost will fulfill two functions - in the short term anticipating where the creature might be (it went in through that passage, it ought to pop out on the other side) and in the long term remembering where the creature was last seen.

This is the creature's "internal reflection of the world", it can never ask the game engine directly for info on where creatures are, but always have to go through this sometimes incorrect filter.

This is the Tracker as it stands after one day of work. The debug visualization is a little wonky because the the laser is only displayed when the lizard sees the slugcat's upper body, but the ghost is set to visible mode on seeing the lower body as well.



As you can see the "anticipation of movement" stuff is not really done yet. In simple cases like this, when there is pretty much only one way to go, the ghost should be able to follow a corridor through many twists and turns. This is where I'm planning on having the tile-based movement kick in - it'll move smoothly until it inevitably gets stuck in a corner, then it will start to evaluate its further movement options on a tile-by-tile basis.

Also the ghost should respect what tiles are considered accessible and inaccessible to the creature being emulated.

The basic framework for creating, maintaining and deleting ghosts seem to be working fine though. This system also potentially allows for multiple ghosts tied to the same creature, which could create interesting options where an AI creature could for example evaluate both options at a road fork or the like.

[gimymblert]

This is certainly overkill but I think you should at least know about this
http://aigamedev.com/open/tutorial/occupancy-grid-prototype/

Occupancy grids are a way to track the player's last known position in a more accurate fashion, by modelling probabilities in a graph-based data structure. These probabilities are calculated using the following steps:

Visibility — When the player is visible, the probability for his/her current cell is set to one. Otherwise, all visible cells (without the player) have their probability reset to zero.

Propagation — If the player is not visible, the probabilities from the previous occupancy grid are propagated along the edges of the graph to neigboring cells.

Using this resulting probability distribution map, it's possible to estimate how likely a player is to be found in a certain location. It allows an NPC in a stealth-like game to perform a methodical search by probability based on where player's predictions.

related
http://aigamedev.com/open/tutorial/influence-map-mechanics/

[jamesprimate]

And now, straight from the island in the Swedish countryside!

Update 282
After talking a little with James, we have started to pin down the AI stuff some. Still I feel it might need some digestion, and have instead started on the next (and last) module that will be shared by almost all AI creatures - the Tracker.

The Tracker module is basically a piece of code that makes creatures be not omniscient. It creates ghosts for each other creature that the creature knows of, and acts as a combination of visual processing unit, memory and anticipation/prognosis intelligence.

As James described, the Tracker runs a ghost for each other creature. When the other creature is clearly visible, the ghost will be updated to its position each frame. When obscured, the ghost will fulfill two functions - in the short term anticipating where the creature might be (it went in through that passage, it ought to pop out on the other side) and in the long term remembering where the creature was last seen.

This is the creature's "internal reflection of the world", it can never ask the game engine directly for info on where creatures are, but always have to go through this sometimes incorrect filter.

This is the Tracker as it stands after one day of work. The debug visualization is a little wonky because the the laser is only displayed when the lizard sees the slugcat's upper body, but the ghost is set to visible mode on seeing the lower body as well.



As you can see the "anticipation of movement" stuff is not really done yet. In simple cases like this, when there is pretty much only one way to go, the ghost should be able to follow a corridor through many twists and turns. This is where I'm planning on having the tile-based movement kick in - it'll move smoothly until it inevitably gets stuck in a corner, then it will start to evaluate its further movement options on a tile-by-tile basis.

Also the ghost should respect what tiles are considered accessible and inaccessible to the creature being emulated.

The basic framework for creating, maintaining and deleting ghosts seem to be working fine though. This system also potentially allows for multiple ghosts tied to the same creature, which could create interesting options where an AI creature could for example evaluate both options at a road fork or the like.

the gif isnt work for me for some reason. anyone else having this prob? i'd LOOOOOOVE to see it

[Slader16]

same here, I don't see a gif 

[Christian]

Ditto, no GIF for me

[gimymblert]

gif for me 

[Whiteclaws]

Image is broken because the link sends us to the site where the image is stored and is actually not the image

Here is the gif

[gimymblert]

this one broken for me lol

[jamesprimate]

Image is broken because the link sends us to the site where the image is stored and is actually not the image

Here is the gif

yooo! thanks this is really cool

people are going to see this gif out of context and be like "COOOOL RAIN WORLD HAS LAZZZERS NOW!!!!"

they'll be so disappointed

[MisfitChris]

da best

[Slader16]

I still don't see anything 

[JLJac]

My usual upload service wouldn't work for some reason, so I had to use another. Here it is again, anyhow:




Update 283
Inspired by the occupancy grid article, I've started developing a solution with another level of hierarchy. Instead of just the tracker owning a bunch of ghosts, each of which knows which creature it's supposed to be emulating, the tracker now have a list of "creatureRepresentatives", and those have a bunch of ghosts each. When the creature is actually seen, this list is shaven off from the second position, and the very first ghost is put at the creature's position. When it's not seen, the ghosts are allowed to mill about.

I now have some basic ghost movement as well. It takes the allowed movements of the emulated creature into consideration, and moves to nearby tiles. It prefers to go in the same general direction as the creature was last seen moving in. When reaching a road fork it will sometimes split into two.

I'd post a gif of a million ghosts splitting over and over until it looked like mayhem, but I'm in the middle of transitioning to the representative system, so the game won't run ATM. Gifs tomorrow!

[JLJac]

Update 284
When reaching a road fork, where one option is considered ideal and the other slightly less so, a ghost is now able to clone itself. The clone gets a slightly lower score, which is accounted for in the eventual ghost ranking process.

Ghosts travel slowly, as we want creatures to assume that their prey is at least somewhere close to where they lost it. Over a large amount of time however, the ghosts will travel to pretty much all corners of the world, which means that a creature that has been long lost will be looked for in much more diverse locations than one that disappeared around a corner just two seconds ago. Each time a ghost travels, it will check if it is in the line of sight of the creature inside which's head it's living. If so, it'll freeze in place - it wouldn't make sense for the the creature to assume that the prey could have traversed any distance that is actually visible to it.

In this gif (trying yet another hosting service, hope this one will work for everyone!) you can see a (stuck) lizard lose track of a slugcat. Notice how after time has been sped up, the possible locations are scattered all over the lower left area, but also contained within the area which is not visible to the lizard. It knows the slugcat has to be in there somewhere, but becomes less and less sure of exactly where as time goes by. Here the ghost count is capped at 15, I think the actual game would generally use fewer.



When the slugcat is actually seen, all ghosts except one are removed. The ghost that's slightly larger and pulsating is the one that's considered the best guess for where the slugcat might be. This is where the ranking comes into play. The ghost score has several things feeding into it. Traveling in the same general direction as the tracked creature was last seen moving in is one, proximity to the last seen coordinate and the tracking creature are others, intended to make search behaviors look more reasonable. The search behavior will probably be mainly about going after this "best bet" ghost until all of them are gone.

When the lizard is moved close to the ghosts, they disappear. Note that they don't disappear as soon as the lizard is able to see them, but the lizard has to be somewhat close as well. This is for a few different reasons. One is that when the ghost cap is reached, and a ghost reaches a road fork, it won't pick one direction, but instead just freeze in place (seemed more reasonable to me to stop at the crossroads rather than picking an option at random that would take you even further away from where the creature was last spotted). Another is that the ghosts are not in every tile in the possible area, like an actual Occupancy Probability Grid. Both of these are generally the same concept; that these ghost coordinates are not strictly "places where I believe the creature to be", but rather "places that would be a good idea to go when searching for this creature" if you get the distinction. The latter can't just be dismissed at a glance, but takes some examination before its hypothesis can be falsified.

Many of the parameters for this whole thing can be customized, such as the max amount of ghosts per tracked creature, the speed of the ghosts (as a fraction of the tracked creature's average speed - I imagine I'll generally want the ghosts to move slower than the actual creatures as a conservative guess that's closer to the last seen coordinate is better than a wild guess) etc.

Ideally this system should also be inter-room, so that a ghost could pass through a shortcut into a neighboring room  - this I haven't implemented yet. But generally I'm happy with the system. I will however add some functionality to dumb it down to work better for the slightly thicker creatures. An example would be that a dumb green lizard probably shouldn't be able to be too clever about how you're able to climb and it's not. Instead it should assume that you have the same limitations it has, and emulate your ghosts with its own terrain preferences. That way when you climb up and away from the area it's searching, the proper reaction should be confusion.

[Rebusmind]

Maybe I have overlooked this detail (I'm very tired), but does the AI also take into account areas that the creature might not know? Or do they know all the areas? Cause in the gif, the ghosts are traversing all the different paths.

[JLJac]

Yep, it's assumed that the creatures have full knowledge of the map layouts. There are a couple of reasons for this. The player has access to the mythical third dimension, allowing them to view the entire room simultaneously, and I think seeing other creatures through walls is quite enough of a head start. Also it kind of makes sense - as the environments are static - for the creatures to know their premises. And, making AI, path finder and tracker account for probability of unknown tiles is a huuuuge pain programming-wise, that would most likely have no pay off in the gameplay aspect except making the creatures behave stupidly and unpredictably. Saving which tiles are discovered would consume massive amounts of memory as well. So, I've decided that the creatures are always aware of the terrain layout, though they are not omniscient as to where other creatures currently are on the maps.

[Rebusmind]

Don't get me wrong, I agree completely with everything you just wrote, I was just curious.

[jamesprimate]

An example would be that a dumb green lizard probably shouldn't be able to be too clever about how you're able to climb and it's not. Instead it should assume that you have the same limitations it has, and emulate your ghosts with its own terrain preferences. That way when you climb up and away from the area it's searching, the proper reaction should be confusion.

classic green lizards!

very cool visualization. how do you suppose that system scales? it is something light-weight enough to run, say, 15-20 instances each with 15 ghosts?

[JLJac]

I think so! Also I've noticed that the search behavior doesn't change much from 2 ghosts and up, so I think 3 or 4 ghosts would be just fine. Also, for creatures that the tracking creature doesn't have much interest in (neither prey nor threat) tracking just 1 ghost or none at all will save some space, if that becomes an issue.

Update 285
Made the ghosts work between different rooms.

Created a system which gives ghosts a "second chance" before dismissing them on visual contact - this second chance consists of scurrying away very quickly hoping to find an obscured tile. This comes in handy when a ghost is sitting for example next to a short cut entrance, in that case it makes more sense to just move the ghost in through the shortcut when it's seen, rather than remove it. Its score is however downgraded, so the hypothesis of that particular ghost is considered less likely.

When I had this "second chance" system in place, I decided to have that apply to the last existing ghost always, and never delete it. This means that the tracking creature will always have some theory about where the tracked creature might be, though the hypothesis is considered more and more unlikely.

By having the lizard follow the "best guess" ghost of the player, I managed to have it display some pretty cool search behavior.



The little pink number is the estimated chance of relocating the player - this will play a part in actual AI decisions later, such as when it's time to abandon a hunt. The chance is calculated using an average number between the amount of ticks since the player was last spotted and the lowest generation among the ghosts (times ten). This means it takes both pure time and how much effort it has actually put into looking for the player into account.

Inspired by the Utility Based AI stuff, I made this curve for evaluating that probability:



Up until the intersection (45 in the image) it follows the red curve, after that the blue one. This means that during the very first seconds it will estimate the chance of re-locating the creature as pretty high, then it will start to drop quickly. Then the blue curve kicks in, which never actually reaches 0, just gets closer and closer to it.

The idea is that the Tracker will always be able to suggest some small chance of finding any given creature and a coordinate to start looking, even though the search is more or less futile. This way I can make sure that all the decisions are actually made in the decision making AI. If the Tracker could "give up" that would essentially mean that the Tracker made the decision to stop looking for that creature, which isn't its job.

Here's a gif of the lizard prototype trying to search for a player that has been removed from the map. The estimated probability goes down, but it could theoretically continue this search for ever and ever unless told otherwise. Note how the search is first focused to the nearby area to where the creature was last spotted, but later moves on to further away areas as all of those options are exhausted.

[Lee]

That's a really complex curve function, would this not do?*:


*I can't really tell because I could't reproduce your graph equations, came out completely differently for me.

Code:

float get_percentage(int time_last_seen){
    float x = (time_last_seen-117)*0.25;
    return 2.25-((x*x*x)/256);
}

Edit: I got the two lines mixed up, you wanted a plateaux at the start: