2
\$\begingroup\$

I am trying to develop a stronger AI for the popular game, Zatacka. The basic aim of the game is to survive the longest. It's like the TRON game, but the characters can only turn smoothly, instead of 90 degree turns.

I am new to game AI. I have the following ideas in mind, but I don't know how they can be implemented.

  • Collision prediction. If another player is about to come into the same area, then the player should turn around and try to evade.
  • Hole taking capability. How to detect holes. How to distinguish holes from a normal empty area.
  • Early detection of a dead end and being able to turn around before its too late. The problem with this how do we determine a dead end, it could be a bit far than our current position. Doing a path finding algorithm and searching for the wall or a player's body might not be efficient enough as this has to be done for each steps.

Are there any standard algorithms for these problems? Can somebody throw some light on how I can approach these problems?

\$\endgroup\$
  • \$\begingroup\$ You need to start by re-inventing the wheel. I'm kidding. Read a book about AI for games. There is actually a pretty good book named "Artificial Intelligence for Games". Learn about steering behavior. \$\endgroup\$ – wolfdawn Feb 15 '14 at 12:25
  • \$\begingroup\$ I have read about steering behaviours. I am able to move the player around. My main problem is on how to handle various situations without slowing down the game. \$\endgroup\$ – Torpedo Feb 16 '14 at 7:23
1
\$\begingroup\$

First of all I would like to say that I completely agree with Willem, specially regarding the suggestion for you to start with a simplification of your problem and that game AI is "much about experimenting with ideas".

Particularly I find Willem's second approach to be more suited to the conditions of your game, in which the environment is very dynamic (specially with more players), making very difficult to plan much ahead. A rule-based solution may work quite well, allowing your agent to figure out the best course of action in a reactive fashion: each turn it can sense the environment (walls, holes and opponents positions) and choose an action that maximizes its goal.

But I would give a try to a solution based on (or inspired in) the subsumption architecture. The basic idea of this architecture is that the agent is composed of different behaviour layers (i.e. that take particular decisions) that are organized and evaluated in a stack from bottom to up. The most "primal" behaviours are positioned at the bottom, with the more general behaviours (that use the ones bellow) on top. All layers may be constructed with a set of finite state machines, producing outputs that may inhibit other layers. The final agent behaviour is the result of the many interacting behaviours.

In that way, your agent may have obstacle avoidance behaviours at the bottom, and opponent chasing at the top. Or something similar to that. :)

Here are some interesting readings:

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks a lot. I think this is one good way to approach it. \$\endgroup\$ – Torpedo Feb 19 '14 at 4:21
1
\$\begingroup\$

Seriously think about is how can you simplify the problem. One simplification is to limit the game to two players (or even one). Another simplification is to use bigger and discrete turn angles and increase time steps. So instead of curves you have lines with corners. Such simplifications may or may not end up in your final AI, but it will help you explore the problem a bit better.

I can suggest two general approaches. These approaches may lead to some specific algorithms.

One approach is to search through a tree of possible future game states (such as A* and minimax). Then based on this search, make an optimal move. Some future states would then predict collisions.

Another approach is to define a set of rules that decide a course of action. Then make an assessment of the current game state, apply the rules and get a course of action based on that.

If you get an understanding of both approaches, you will probably see that they can be combined in crazy creative ways :). AI is much about experimenting with ideas.

\$\endgroup\$
  • \$\begingroup\$ I thought abt A*, but I felt it would be too expensive as basically my output for the AI movement is either a right or a left or continue straight. So for each frame, if I do the entire calculation, it might be expensive for me. One of the greatest problems I see is that the map keeps changing.. \$\endgroup\$ – Torpedo Feb 16 '14 at 7:10
  • \$\begingroup\$ AI might require you to create a separate thread. Think about the AI as someone that writes something on a blackboard. On each frame you quickly check the blackboard to decide what to do. Yes, things change all the time, that is why you have to say something like : "I want to plan ahead for 3 seconds, assuming that every player makes only one turn change per second". Much less expensive. \$\endgroup\$ – Willem Feb 16 '14 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.