Game AI

Nithin.S

Hi,

i am currently working on a simple first person shooter game and this is the first time i am at it. I am actually working on the AI part where the enemies must find the correct player and attack, I have seen some shortest path algorithms like A* and it's variants

I want to know in which manner or format the MAP must be stored and conveyed to the CPU players so it is efficient.I want to know this because in a complex map there may be a lot of crucial points and terrains..

Inaki Ayucar

Your algorithms will get much more simple if you manage your path finding algorithm and everything just in 2D instead of 3D.

To achieve that, you can store pre-computed information in a 2D map of each part of your scene. That map can include whatever you want (inaccesible areas, obstacles, etc). A typical example is the Height Map, which stores the height of the terrain at each point. This case is very frecuent in racing games. Of course, the map is indexed using the world coords (X,Y) of the player position and can be as accurate as you want (the more accurate, the more memory your map will use, of course).

In the height map example:

Player¡¯s position --> (x,y)

Terrain¡¯s height at player¡¯s position = HeightMap[ x ][ y ]

You can even do some kind of interpolation between the values of the point you¡¯re looking for and it¡¯s neightbours.

To workaround the 3D-2D issue, you can divide your scenes so each part never has more than one height level. For example, if your scene is a building with 6 floors, it can be divided in 6 parts, so each one will have only one map.

This way, the path finding algo. will be much easier.

Regards,

Inaki Ayucar

Didn¡¯t say this before, but when accesing the Map, you cannot of course just plug player¡¯s position into the array indexers. You have to search for the closest point in the map. For example:

Player¡¯s position = (0.3453, 0.2556)

Closest Point in Map = (0.3, 0.25)

Height at point = HeightMap [ 0.3 ] [ 0.25 ]

Cheers!

Nithin.S

Thanks for the tips.

Inaki Ayucar

You are welcome. If you find that info helpful, could you please mark the post as answered

Thanks.