Let's say you have a game. The game is a 2d platformer with NPCs that should be able to walk back and forth. They also should know how to NOT fall off the platform's edge. How do we solve that?
At first glance it seems we might just make them go in the desired direction and turn them around when they're close enough to the edge. But what if platforms can have gaps between each other? Gaps small enough that more appropriate behavior for the NPC would be to walk over them? How do you teach your AI to identify whether they should keep going or turn around? Most importantly - how do we solve that while having good performance? Here's a lonely NPC standing on the platform in confusion:
See the Pen AI navigation article part-0 by lightest (@lightest) on CodePen.
Thinking by analogy suggests to build some kind of vision system. Then NPC would detect it's surroundings at a certain distance then it would identify a platform that is close enough and at the same level as the one it's currently walks on then it can keep walking. Each of the NPC instances would have to do all of these AT LEAST 60 frames a second. While modern computers are fast it seems there has to be a better way of arriving to such a simple decision as "to go or not to go".
Thinking in first principles suggests to reason up from simple truths. We know for sure that the atomic operation each NPC should do is to decide whether to keep going or turn around. Let's start from basic case when there are only one platform. As we assumed previously it would be enough to compare NPC's position against each edge of the platform. If NPC is close enough i.e. the difference between NPC's position and the platform's edge is low enough it can turn around. In the example below this references NPC, this.x it's left edge, this.right it's right edge:
if(this.x - floor.x < game.settings.platformEdgeThresh) {
this.x = floor.x + game.settings.platformEdgeThresh;
this._direction *= -1;
} else if (floor.right - this.right < game.settings.platformEdgeThresh) {
this.x = floor.right - this.width - game.settings.platformEdgeThresh;
this._direction *= -1;
}
See the Pen AI navigation article part-1 by lightest (@lightest) on CodePen.
Knowing the limits of surface an NPC walks on allows for simple check to make a decision. We could achieve more complex behavior while preserving simplicty of computations if we could somehow figure out what are the limits of some common surface formed by gap separated platforms. Identifying which platforms can be united in a single surface is our starting point. We do that by checking if two platforms have same Y position (which is their top edge) and small enough gap between them.
loadPlatforms (platforms) {
var i, j, gap;
for(i = 0; i < platforms.length; i++) {
this.addObject(platforms[i]); // adds platform to the global storage
for(j = i + 1; j < platforms.length; j++) {
if(platforms[i].y !== platforms[j].y) {
continue;
}
if(platforms[j].right < platforms[i].x) {
gap = platforms[i].x - platforms[j].right;
} else if(platforms[j].x > platforms[i].right) {
gap = platforms[j].x - platforms[i].right;
}
if(gap <= game.settings.surfacePlatformGap) {
}
}
}
}
Our choice of how small a gap should be is dictated by NPC's average size and their movement speed. Really fast, skinny NPCs can hop over large gaps whereas fat, slow NPCs will cover gap distance with their body. In our case game.settings.surfacePlatformGap = 10. This gap along with Y equality together form a safety condition.
Next step is to find out the best way for the NPCs to access common surface information. In a regular 2d platformer an NPC always knows which platform it walks on due to collision detection. As soon as NPC touches the floor some sort of handling function gets triggered resulting in NPC always having fresh data about the platform it walks. This means querying the floor platform itself for existing common surface is our way to go. Let's finish the loadPlatform function:
if(gap <= game.settings.surfacePlatformGap) {
if(platforms[i].surface !== undefined && platforms[j].surface !== undefined &&
platforms[i].surface !== platforms[j].surface) {
surface = this._mergeSurfaces(platforms[i].surface, platforms[j].surface);
platforms[i].surface = surface;
platforms[j].surface = surface;
} else if(platforms[i].surface !== undefined) {
platforms[i].surface.expand(platforms[j]);
platforms[j].surface = platforms[i].surface;
} else if (platforms[j].surface !== undefined) {
platforms[j].surface.expand(platforms[i]);
platforms[i].surface = platforms[j].surface;
} else {
surface = this._instantiateNavigationSurface(platforms[i].x, platforms[i].y);
surface.expand(platforms[i], platforms[j]);
platforms[i].surface = surface;
platforms[j].surface = surface;
}
}
By expanding common surface with platforms based on their safety condition we achieve common surface that is 100% safe to walk. Because the surface instance has same fields as a regular platform we achieve perceivably smarter behavior at the same per NPC computation cost. The idea of this technique came to me in the process of Dangerous Dave replica development - a programming exercise I conducted in 2015. The replica is available here. At that time I named such surfaces "Navigation Surface" as the surface an NPC can reference to get the idea of how to navigate the world. Few days later I found out the exactly same idea is used in 3d games under a bit different name - "Navigation Mesh" since the shape of the suface is more complex and described using mesh. More information is available here.
Now let's put it all together. As soon as NPC touches the floor a collision handling function gets invoked and provides floor platform instance. By querying it for navigation surface an NPC then will perform an edge proximity check against that surface or in case of absence against the floor platform itself and eventually will make go/nogo decision. In the example below this references NPC and object is something NPC collides with at the moment:
handleCollision (object) {
var floor;
if(object.y > this.y) {
this._touchingFloor = true;
if(object.surface !== undefined) {
floor = object.surface;
} else {
floor = object;
}
if(this.x - floor.x < game.settings.platformEdgeThresh) {
this.x = floor.x + game.settings.platformEdgeThresh;
this._direction *= -1;
} else if (floor.right - this.right < game.settings.platformEdgeThresh) {
this.x = floor.right - this.width - game.settings.platformEdgeThresh;
this._direction *= -1;
}
}
}
NPC safely walks over platforms separated by various gaps:
See the Pen AI navigation article part-2 by lightest (@lightest) on CodePen.
Navigation surface is shown as rectangle outlined with black. You can play around with platform's positioning to see various surfaces our function creates from them. Also make sure to see what happens if game.settings.surfacePlatformGap is set to be too large :)
Top comments (0)