Tag Info

Hot answers tagged

7

A* would work fine for this task, but since your map is small, Breadth First Search would work too, and it's even simpler than A*. These are “graph search” algorithms, which require you to tell them what the allowed moves are. They are not limited to grids. In your case you would tell it that the allowed moves from (x,y) are to (x+1,y-1), (x+1,y), and ...


2

For the A-star algorithm you must provide a data structure that, for vey legal current position of the agent, provides the set of possible moves from that location along with the cost of making that location change. The most common means of providing such a data structure, especially for a rectangular grid, is a 2D array of lists. However for more complex ...


2

It might be helpful to think of the key variable as a stack that you're trying to count the depth of. Every iteration, you add 1 to the depth, return if the stack is empty, then pop 3 bits off the stack. The sentinel bit just marks where the stack ends. An example (imagine lots more zeros to the left): ... 001 000 010 111 # pop 111 ... 000 001 001 010 # ...


2

There is no 'best' solution to this problem. Ultimately you're going to have to find by trial and error something that gives the best tradeoff between performance and believable intelligence. However if you want to use any sort of path finding algorithm you're going to need to subdivide your world in some way. Whether you go with tiles, polygonal zoning or ...


1

To make it easier for you to switch between world coordinates and grid coordinates, you should make two functions, projectToWorld and projectToGrid. pseudo code: /** * returns the topleft position of a given grid coordinate. */ function projectToWorld(gridX, gridY) { return new Vector2(TILE_WIDTH * gridY, TILE_HEIGHT * gridY); } /** * ...


1

A* will certainly work for this. Linked below is an excellent tutorial on how to implement it. 1) Add the starting square (or node) to the open list. 2) Repeat the following: a) Look for the lowest F cost square on the open list. We refer to this as the current square. b) Switch it to the closed list. c) For each of the 8 squares adjacent to this ...


1

I'm not sure I completely understand what you are asking, as it's hard to tell what you mean by your "game style", but I will say that a path-finding algorithm is not necessarily overkill, especially if you would like your NPC's to find specific routes around obstacles. From my own experience with AI navigation, there are a couple of very popular types of ...



Only top voted, non community-wiki answers of a minimum length are eligible