vrijdag 20 december 2013

Do not forget AI

In one of our earlier blog posts you could read about textures being very, very important. Now I do not disagree with that but another important aspect of our game is Artificial Intelligence, or AI in short. AI is a big subject, it contains every action the enemies can perform. From when and how and where to attack to a simple where do I go now. We do not think AI should be too smart but we also want it to be realistic. I do not think I have to tell you that it will be hard to make such an AI.

We will implement a system that uses the shadow casting (seen in one of the earlier blogs) to enable the player to go by enemies unnoticed or even ambush them. Now I know that this is a really big goal we are setting here. However, for our game to be successful we need a good and solid AI. One that doesn’t see you enter their room and then simply start running towards you and attack. At the moment that is exactly what they do because I have been busy making an algorithm for our path finding.

That is right, meet the new lead AI programmer: ME.

We need pathfinding for navigating the tight corridors in the levels. I want to make pathfinding work first because we cannot have enemies trying to look for the player while they get stuck every time. Now there are a lot of powerful pathfinding algorithms but our game does not need an algorithm that strong so we agreed to use the A* algorithm. While I will shortly explain the A* algorithm.

We begin at the Playertile (the grid location of the player) and we look at all the Tiles (blocks in grid) neighboring it. If none of these Tiles contain something we cannot walk through we go to the next tile. Once we find a walkable tile we calculate its F value. The F value is calculated by taking the cost of moving to that tile from the Playertile: G (we use 10 for vertical and horizontal movement and 14 for curved movement) and adding the estimated movement cost to the enemy: H. We then add this Tile to our Open list.

If all the adjacent Tiles have been looked at we add the Tile with the lowest F to a list we call Closed. We also save which Tile this Tile was looked at from (its Parent Tile) we will need this later.

Now we look at all the Tiles surrounding the Tile we just saved in the Closed list. Apart from the procedure above we now also need to check if the Tile we're looking at is in the Closed list. If it is we should look at the next Tile because we already looked at those and they are already on our path or lead to a dead end. Also we need to make sure it is not in our open list because we already have data for those tiles, however if it is in the Open list we must check if the G value of that Tile is higher than what we calculated from the new Tile. If it is higher then there is a better path to that tile via the Tile we now look from.

We continue this until either we run out of possible tiles or the Tile with the lowest F is the Enemytile (Grid location of the enemy) we then take this Tile and add it to the Path list. Then we add its Parent Tile, and the Parent's Parent Tile and so on until we add the Playertile. Now the enemy simply has to go to every location on the Path list and it will arrive at the Player.

Pathfinding is really cool and all but here in the Netherlands we have a saying "waarom moeilijk doen als het makkelijk kan" which means "why do it the hard way if you can do it the easy way". Now this also applies to Pathfinding because if there is no obstacle between the player and the enemy, then why should we use pathfinding? The answer is simple: We do not. We use a Raycast written by Timon to check if there are obstacles in the way. If there are no obstacles we simply make the enemy go directly to the player.
There is just one more thing i would like to add. We now have a new enemy: THE BANDIT

He will club you to death if you do not watch out!

Geen opmerkingen: