Peripheral vision

I’ve checked the project plan to see what features I had left to implement and found out that I’ve written the plan a lot less detailed than I remembered, the fact that you as a player should be able to hide beneath something is never mentioned. So according to the project plan, all required features of the project have been implemented!

So with time to spare I’ve started to improve the agent even more. The most obvious flaw for now is that the agent have a very narrow vision. So if the target is close to the agent and slightly to the side it’s never spotted. To combat this I plan to use the same system as in Thief: The Dark Project, where each agent has several view cones to emulate focus, peripheral vision and such.

One quick idea I got where to move the near clip plane of the agents camera. By increasing the distance, the near clip plane will increase in size, resulting in a wider area of vision close to the agent, perfect!

A view frustum. Each side is a clipping plane.

I got it working, but I didn’t quite think it through. With a wider plane, the plane will start to clip through walls. This results in that the agent can look behind walls when it turns around and the near plane spans across both sides of a wall.

So in the end I’ve done it exactly like Thief with several view cones. I got one for the peripheral vision and one for direct vision. Direct vision is used to cover the area close to the agent that falls outside of the view frustum. An entity is added to the view cone of highest priority it exists in so if an entity is inside both cones it will only be added to one. Entities inside the direct vision is added to the list of visible objects. What I’m going to do with entities inside the peripheral vision isn’t fully decided. For now the idea is to increase the probability at those locations causing the agent to gain a higher interest for those areas.

Oh, and I finally added the ability to reset the level. So now I doesn’t need to restart the application every time I’ve need to test something several times.

Looking beneath objects

The end of the week is here. The goal this week was to finish the logic system. I would say that is the case as these past few days I’ve only been implementing the behavior of the agent. The system works and can easily be extended with more behaviors and goals for the agent at a later stage.

So far the agent can:
Roam around to find the player, this uses the POM to steer where the agent should look.
Follow the player, as long as the player is visible for the agent, it will follow.
Search for the player, uses the last memory of the player and the POM to steer it’s search.
Look beneath objects, if the player goes somewhere the agent can follow, i.e. hides beneath something, the agent goes as close as possible and bends down to look at the player.

The last behavior isn’t fully functional. For now, the agent goes to the closest position and bends down. But what if the player hides in a tunnel, where only two sides is open and the closest position is next to a tunnel wall? The agent should realize this and try to look through the tunnel at one of it’s open ends. The plan for now is this:

Straight from my position, is it possible to see the target if I bend down?
Yes? The go straight ahead and bend down.
No? Where did the target enter? Go to that position and then bend down.

This will make it seem like the agent is aware of the fact that there’s specific openings to look through.

Behaviors

This past two days I’ve been hard at work on the logic for the agent.

As I mentioned earlier there was a need to redo the pathing of the agent. This was the first thing I finished. After that I threw together a quick goal-driven logic system to implement the easiest action, namely hunting the player. It might sound like a big thing, but when you think about it, it’s all about following a target if I see it. If I can’t see it, some other behavior can take over.

It was quite easy to get functional, and by implementing this basic system I had a better idea of how to design the whole creature system. It consist of three major parts, Sensory Systems, a Working memory and logic. The sensory system feeds the working memory with MemoryFacts about the world. For this project only the vision system is implemented, so raw data about what have been seen is used to create a VisualMemoryFact, it saves away the entity seen, the position it was observed at and the velocity it was traveling at. It’s easy to extend with new types of memory facts for say sounds or smells. When a memory fact is added to the working memory, it is compared to the facts already in the memory to detect if the new fact is just an updated version of an already existing memory. I’ve also added StaticFacts as I call them, they’re used for things the agent should always have knowledge about, such as the POM, the entity it’s hunting for and such.

The logic system then uses these memory facts to act upon. In a perfect world, no queries to new data, say the entities current position, should be made from the logic system. However in reality I have to do it at some occasions as the visual data is gathered on the render thread, so there’s a bit of delay between memory updates.

To get it all into Nebula I use a property to act as the “brain” and glue it all together. It contains the working memory for the agent and takes care of translating raw sensor data into specific memory facts.

Normalization issues

I fixed the problem with the probability growing beyond 1. As I sat down with a clear head this morning I divided up all parts of the calculation so I could inspect each intermediate result. The error lied with how the probability where divided to each nodes neighbor.

In the initial formula the diffusion constant where divided by a constant number multiplied with the sum of probability gained from neighbors. This constant number where the amount of connections to a node. The nodes in my map has a varying amount of neighbors so I just replaced this constant with the amount of connections this node currently have. What was a problem is that the formula described how to update the probability of a given node so it’s when I replace the constant with the current node connections that the problem occur. That whole part reflect the amount of probability gained form neighbors but the constant describes the probability given to neighbors. So to fix it, instead of getting the sum of a nodes neighbors probability and then multiplying, I let each neighbor do the whole calculation and give me the exact sum this specific node will give to a neighbor.

I then went on and tried to implement a velocity based spreading. It causes the probability to spread more in a given direction such as the last seen direction the target was moving in. I got it working but also here I had problems with the probability growing over time. In the end I just got tired of it so now after the new probability have been calculated it’s renormalized before culling of the visible nodes is performed.

I don’t know if this will come back and haunt me later but things seem to be working as expected for now.

Milestone 2

So…

I haven’t done too much today, as it was milestone two today and the whole afternoon was spent listening to all presentations and also doing my own.

I did get some valuable feedback on my project. Not really on what I’ve done but on what I will do. The goal now is to create the real sight sensory system for the agent that will function in fully 3D and not just on the XZ-plane as it currently does. The reason for fully 3D vision for the agent is so it can decide if it sees the target or not and also be able to look beneath objects.

The plan is to use synthetic vision by which one render a crude representation of the scene from the agents point of view with objects color coded. The problem arise in that one need to scan over the rendered scene to be able to tell what been seen. The tip I got where to downsample the rendered image without blending the colors. This will resolve in a much smaller buffer to scan through at the loss of precision of objects spatial locations. But as I’m only interested in what I’ve seen and not where as I can easily obtain that information in other ways I can get away with this. Synthetic vision will also be a great way to showoff the agents inner workings.

To get the agent to look beneath objects I plan on render the POM at several heights so it will become a 3D grid visually but stay in 2D logically. Each node will contain flags on which level it is visible, so a node can be inside an object at one level but still remain visible and active at the other levels.

Getting there

I’ve finally gotten the occupancy map to such a state that I could call it finished. This Friday I added a basic 2D viewcone for the agent so I can simulate vision on the grid. This is needed as the POM works with expectations theory and as such there is three possible outcomes for a verification of an expectation, verifiably true, verifiably false and unverifiable. So what I’ve implemented is the impact of negative verification on the grid, ie, we have verified where the target isn’t located, so this will now impact where we should look next. This will later be extended to support real 3D sight for the agent.

iseeyou

Over the weekend I did a lot of refactoring, something I see as crucial for my own sanity as I will be working with this code for quite some time. I also moved the path-finding from DetourCrowd into a custom game entity property in Nebula. I had some problems with actually getting the agent to move, the path-planning worked but the agent stood fixed in place. The problem turned out to be a variable that defaulted to 0 so the agent didn’t gain any velocity.

Occupancy Grid

Today I’ve mused over the probabilistic occupancy grid. While waiting to get access to Nebula I put some time into examining Detour, the path-finding used in the engine. As the creator of Detour has made the excellent nav-mesh generator Recast it would be a shame not to use it. However, a nav-mesh has too large areas to really be usable for an occupancy grid so I’ve looked into the possibility to generate a more grid-like structure.

This is indeed possible but not that straight forward. So far I’ve managed to generate thin stripes over the different walkable areas. Tomorrow I’ll try to extend them to form an actual grid structure.

Agent design

This past week have been used for researching different alternatives on how to design the AI. I’ve divided the project in to three major parts, namely: search behavior, senses, and logic.

For the search behavior I landed on using a Probabilistic Occupancy Map or POM for short. After seeing the video available at AiGameDev, which pretty much showcase the exact behavior I want for my agent, the decision where quite easy. It doesn’t seem to have been used in large game as of yet, at least I couldn’t find any verification of it. It have however been used in various research projects and as the video shows it is feasible in the type of condition I have, a single agent searching a single target.

For the senses, or sense as vision is the only planned one for now, things haven’t been quite as straight forward. I’ve been torn between two different ways to do it, one I made up myself, where you use a octree for partitioning the open space, and check against the agents view cone/frustum to know what areas that have been seen in 3D. The gain for doing this is that I can divide up the space according to physics meshes, so a table will have open space beneath it. The other way is to use synthetic vision where you render the world from the agents point of view with objects color coded. It isn’t as straight forward on how to get information about what the agent has/hasn’t seen. For now I’ve decided to go with synthetic vision as it doesn’t add another data structure such as the octree and I can easily get all seen objects. To get seen areas, a point can be translated from the view to a 3D coordinate or a POM node. I’m still unsure on how to get the agent to look beneath objects. The idea I got now is to have several points for each node at different heights, disabling points that’s inside objects, and have the agent try to see all points for a node.

Logic, which I first thought would need the most work have turned out to be the simplest. As the agent only has one goal, to search for the player, no advanced goal planner is needed. And as searching for the player and hunting it is practically the same (go to the location with the highest probability) it simplifies things even further. To add a working memory to the agent it is in its simplest form only needed to save away an objects id, position and the current time.

So what I’ve discovered is that the hardest part is getting the senses to work with what the agent expects from the world (the probability map). Things are not as simple as I make them sound but at least I got a plan.