1

I am new to game programming I currently am using unity's 2D power to remake an 2D game for sake of practice. So I am just little confuse about one thing, so far every enemy in my game was dumb(they move on predefined paths) but this enemy, alien-copter, flies and follow the player wherever the player goes. My question is should I implement any pathfinding algorithm? I had studied A* but I trying to figure out if A* is gonna be helpful in my envoirnment because player will be moving and the enemy have to keep on looking for shortest path. I tried to write code for this AI my code was working perfect when there were no obstacles but my game has obstacles so I want something efficient so what do you people think should I implement A* or any other algorithm or not?

Improve this question
8
  • A* and Dijkstra's algorithm are probably just fine. Algorithms like these are used on quite large scales, including path finding for navigation systems... in your game you should have no trouble. Commented May 30, 2015 at 14:07
  • Thanks for the response, so A* or Dijkstra they will be fine even when target is moving or changing its position before the enemy could reach it? Commented May 30, 2015 at 14:21
  • Maybe you need something more specific than either A* or Dijkstra's; but o know if that is actually the case you need to be much more specific on what behaviour you wish to have the AI exhibit. Also you might consider asking this question on gamedev.stackexchange.com as well, where developers primarily interested in Games hang out. Commented May 30, 2015 at 14:50
  • @DaniyalAzram Well, you usually compute the path once and then move along the path. If you derive (significantly) from the path, you recompute. Recomputing shouldn't take you long though. Commented May 30, 2015 at 15:50
  • @Pieter Geerkens Okay thanks for your suggestion I had asked it on gamedev.stackexchange.com (at)atlaste I was thinking to move enemy to every next shortest block on grid(talking about A*) but it seems that I have to make a path first and then move the enemy on that path Commented May 30, 2015 at 18:01

1 Answer 1

Reset to default
1

As regards AI, if you have obstacles in your game, you will need to implement pathfinding of some sort. Note, that just taking the shortest block (node) is not an option because such algorithm is not complete, i.e. the path may not be found even if there is one. Imagine a going after b:

████████
   a  ██ b
████████

The shortest (best) path is to the left since up, down and right are blocked. On the next move however, the best move is to go right because it's closer. That's how a will get trapped in a loop. So yes you are right, you do need to get the path from a to b. It will typically be in the form of a list of nodes. Then you just select head (aka element at index 0) of the list.

A* is the perfect option in your case. It is complete, efficient and it will even give you the shortest path. Path recomputation shouldn't be an issue for a small game. Furthermore, if obstacles in your game grid are static for the duration of the game you can precompute paths and cache them. For instance, path from (x,y) to (x1,y1) is [(a,b), (c,d) ...]. So you can store it in some sort of map data structure where key is the two points - start, target and value - the path. This will of course depend on whether you want to classify an enemy as an obstacle for other enemies and other gameplay factors

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thank you very much that is the answer I was looking for. My obstacles are static(they don't move if that is what you meant), my enemy flies freely with floating values of x-axis and y-axis and I think A* works with exact values(this is my level of understanding of A*) so will A* be suitable? I think I can modify A* to my needs but just asking if this can be done.
It doesn't really matter in which format you store x and y values, as long as there's some sort of grid behind all this where you can map the positions to. For example a tile's position might be 0, 0 and the size of a tile is 40x40, that means any value between 0 and 40 (including floats) will still belong to tile at position 0, 0. I recommend that you find some open source A* implementation which you can then convert to your language of choice.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.