AI navigation around a 2d map - avoiding obstacles

Question

I know my question seems pretty vague, but I can't think of a better way to put it, so I'll start off by explaining what I'm trying to do.

I'm currently working on a project whereby I've been given a map and I'm coding a 'Critter' that should be able to navigate its way around the map; the critter has various other functions, but those are not relevant to the current question. The whole program and solution are being written in C#.

I can control the speed of the critter, and retrieve its current location on the map by returning its current X and Y position, I can also set its direction when it collides with the terrain that blocks it.

The only problem I have is that I can't think of a way to intelligently navigate my way around the map; so far I've been basing it on what direction the critter is facing when it collides with the terrain, and this is in no way a good way of moving around the map!

I'm not a games programmer, and this is for a software assignment, so I have no clue about AI techniques.

Here's a link to an image of what the maps and critters look like:

Map and Critter image

I'm in no way looking for anyone to give me a full solution, just a push in the general direction on map navigation.

Answer 1

Well, there's 2 different ways you can consider going about this. One is where the AI 'cheats' and knows the entire layout of the map. The AI then just picks what it thinks is the fastest route to its destination, and follows it. The other way is to make the AI "see" the things near it, and navigate based on those. This second option is a bit harder, but can also make games feel more realistic. For your specific case, we're going to use a bit of both!

Outside of NavMesh, a semi-popular method you could use would be to set up waypoints. Waypoints are positions around your map that would allow any character to move to any position on the map by only walking on pre-set nodes. By moving to the closest node to your target, the player, for example, you can then stop using waypoints and directly charge at the player, as nothing would be in the way. And if something gets in the way, just go back to using waypoints! The trickiest part is deciding which route would be the quickest. This can be done by using a for loop to loop through each possible route, and seeing which one is the shortest, or by using A* with it to choose for you. The image below is a good representation of how this would work.

Now you could also do this without the AI knowing the layout of the map. This becomes tricky, however, as making it function well can be difficult if your map is very active, but it has the benefit of being able to avoid non-static objects, which is a downside of navmeshes. This can be done by using several raycasts(Raycasting is commonly used in video game development for things such as determining the line of sight of the player or the AI, where a projectile will go, creating lasers and more. A ray cast is, essentially, a ray that gets sent out from a position in 3D or 2D space and moves in a specific direction) in different directions to probe the environment ahead of the AI, and it can use this data to see how far walls are from it, and then turn to avoid them. This would require your AI to "think" a bit more, however. If the raycast on the right shows it's hitting a wall within a few meters of it, you should probably turn to the left a bit. If both sides are getting hit, keep going straight. And if there is something in front of you, turn whichever directions raycast has the furthest distance, and keep turning until you can go straight again. This logic works great on open maps and fails on very closed space maps or maze-like areas. It's best to have maps either open or closed, but not both. If it's unavoidable, you could just change the pathfinding method when it enters specified zones, so that it can navigate them better. Below is an image of how your raycasts would look, and help visualize how it would help navigate past an object.

For the algorithm in C#, refer the following link:

https://www.red-gate.com/simple-talk/dotnet/c-programming/pathfinding-unity-c/