CODEWITHSUNDEEP
algorithm2dpath-finding
Einarsson
Einarsson

Reputation: 522

2d grid reachable destinations

Let's say I have a 2d grid. Pathfinding is a secondary step in my problem.

My thing is, lets say I have a unit in the middle of the grid. I want to be able to tell the user "These are all your available destinations.".

Based on how many squares the unit can walk, I want to show the user, "these are all the squares you can reach." and then pathfind the destination the user picks.

What's the best way to do the first search to show the reachable destinations?

The terrain can also have limits och bonuses depending on terrain.

I don't know what this is called so pointers on where to look or what to google would be greatly appreciated.

Cheers! :)

/E

Upvotes: 3

Views: 2166

Answers (3)

hugomg
hugomg

Reputation: 69984

For each point in the grid, store:

  • The minimum distance from the unit to this point.
  • The next step towards the unit in the shortest path.

To calculate this, do a breadth-first search:

  • Set your unit's point distance cost to 0 and its "path pointer" doesn't matter/null.
  • Create a queue and put the initial point in it.
  • While the queue is not empty:
    • Take the next point and propagate it (look at all the neighbors. If going to them through the current point is profitable, set their distance/path and add them to the end of the queue)

Remember to pay atention so you stop the search after the correct number of steps if you have a limit.

If you do this correctly you can find all the reachable points, find how long their distance is and also have the shortest path available (although it is stored "backwards")

Don't do depth-first search for shortest-path problems! You will likely Do many repeated calculations over and over again. (Unless you are using more advanced heuristic algorithms, such as A* - but then you should already know what you are doing anyway)

Upvotes: 2

Juraj Blaho
Juraj Blaho

Reputation: 13471

Mark connected cells with same numbers and not connected with different. You may find a two pass algorithm for marking the cells at http://en.wikipedia.org/wiki/Connected_Component_Labeling . If the cells are different number, player can't reach that location.

Upvotes: 0

Elva
Elva

Reputation: 1033

The best way would probably be depth first search (http://en.wikipedia.org/wiki/Depth_first_search) with a limit on how far away you can go.

Upvotes: 4

Related Questions