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?

Daniyal Azram
  • 151
  • 1
  • 7
  • 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. – atlaste May 30 '15 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? – Daniyal Azram May 30 '15 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 http://gamedev.stackexchange.com/ as well, where developers primarily interested in Games hang out. – Pieter Geerkens May 30 '15 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. – atlaste May 30 '15 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 – Daniyal Azram May 30 '15 at 18:01
  • Also remember two points: Even when using A*, one always has the choice of heuristic, and the choice of target. One possibility for a multiple agent single target scenario is to have the agents target the cells adjacent to the Target,to avoid/minimize collisions as they converge. – Pieter Geerkens May 30 '15 at 18:45
  • look here [A* in C++](http://stackoverflow.com/a/23779490/2521214) as the player moves then you have to recompute the path periodically ... – Spektre Jun 01 '15 at 07:11
  • @Pieter Geerkens Thanks for being helpful I will also search about different heuristics. I have read about "as-the-crow-flies" on gamedev.stackexchange.com – Daniyal Azram Jun 01 '15 at 14:24

1 Answers1

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

Community
  • 1
  • 1
AlmasB
  • 3,377
  • 2
  • 15
  • 17
  • 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. – Daniyal Azram Jun 01 '15 at 14:38
  • 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. – AlmasB Jun 01 '15 at 15:17