RSS

AI Steering behaviours (evading, pursuing, weighted wall avoidance & wander, arrive, seek) A* path planning and path following (C++, Direct3D/2D)

29 Aug

Features:

  • Evade & Pursue steering behaviours
  • Seek and arrive steering behaviours used to implement other behaviours.
  • Weighted wall avoidance and wander steering behaviours
  • A* path planning
  • Path following steering behaviour (using the seek steering behaviour)

Description:

This project looked at two things common to AI in video games, steering behaviours and path planning. The path planning uses the industry standard A* path planning algorithm. Given the scenario, the heuristic chosen was the Manhattan distance heuristic, although the heuristics (such as Euclidean) can be very easily used. The path following steering behaviour then uses this computed path to follow it, moving from one node to another when it gets close by and stopping gradually once it gets close to the final node using the arrive steering behaviour, which stops entities stopping abruptly or overshooting their target.

The steering behaviours are force based, they implement the desired behaviour by exerting certain forces upon the entity to which it wishes to observe a certain behaviour. Evade runs away from a predator if the predator gets too close but doesn’t just run in the opposite direction, it estimates where it will be in the next turn and runs away from that position instead. Pursue similarly doesn’t just run after a prey, it estimates where the prey will be in a short time and runs towards that. Wall avoidance does just as the name implies, it avoids bumping into walls. This is blended using weights with the wander steering behaviour which simulates “random walks” that patrol men might do. It is weighted such that when near a wall, the wall avoidance behaviour gets a larger share of the force to apply to the entity.

This project also attempted to implement Goal Oriented Action Planning but was scrapped in the end as it was deemed (by me and the lecturers) to be too large to implement in the time given. One day however, I will definitely implement this marvellous planning architecture.

One thing to note, I couldn’t help but notice that the results (as can been seen in the videos below) do make the above features seem easy to implement as it appears not much is going on. However, do realise that AI is meant to look natural and the more natural something looks, the less impressive it will look to us too. I didn’t find these algorithms all too hard to learn and implement but it’s still somewhat high in the list in terms of complexity. I found it easier to implement a continuous level of detail system using tessellation than to implement some of these things!

Media:

Evade demo – I control the red guy whilst the CPU controls the green guy which will try to evade me if I get too close to it.

Pursue demo – each red guy tries to pursue a green guy who try to run away. I should have made the world toroidal in this example so it doesn’t lead to cornering.

A star path planning and path following demo – A path from one point to another is created and the guy follows it. Once he reaches the destination he will (try to) create another path from his current position to some other point. If there is such a path, he will then follow it.

Code is available by request to the companies I have applied for. Please contact me by email, landline phone or mobile phone using the details on the C.V. I sent you.

About these ads
 
1 Comment

Posted by on August 29, 2013 in C plus plus, Direct3D, DirectX, Programming

 

Tags: , , , , ,

One response to “AI Steering behaviours (evading, pursuing, weighted wall avoidance & wander, arrive, seek) A* path planning and path following (C++, Direct3D/2D)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

%d bloggers like this: