CODEWITHSUNDEEP
calgorithmperformanceartificial-intelligence
DividedByZero
DividedByZero

Reputation: 4391

Finding the most natural route between two points on a grid

How can I find the most natural route (something a human might take) between two points assuming that I have an array of bytes, with each bit representing a fixed size square and indicating whether it is accessible or not? For example, assuming the array represents the following grid:enter image description here

Where grey squares cannot be crossed, I need an algorithm that would find the path indicated by orange squares, not that represented by brown squares.

Notice that, whilst the orange path is also the shortest, that is merely a bonus, not a requirement. I simply need to find the path with minimal changes in direction (achieving a decent balance between length and changes). Also, the algorithm must not require large amounts of memory, as it is to run on an embedded chip.

EDIT: As pointed out by Rudy Velthuis, I haven't exactly explained what I meant by "natural". By natural, I mean a path that isn't too long and only requires the user to change direction a few times.

Upvotes: 4

Views: 219

Answers (3)

manlio
manlio

Reputation: 18902

A* is the way to go, but you should consider that it requires some hacks to produce "natural" paths.

Since your map allows diagonal movements the heuristic can be something like:

/* "Octile" heuristic */
int h(node n)
{
  int dx = abs(n.x - goal.x);
  int dy = abs(n.y - goal.y);

  if (dx > dy)
    return 14 * dy + 10 * (dx - dy);
  else
    return 14 * dx + 10 * (dy - dx);
}

Even with this heuristic you're running into ties: SW, SW, SW, W, W, W having the same cost as SW, W, SW, W, SW, W (which looks better).

There are some quick hacks to work around this problem (tie breaking).

They're described in Amit's page (which contains a lot of information and a wonderful introduction to A*).

Upvotes: 2

n. m. could be an AI
n. m. could be an AI

Reputation: 119877

Build a graph where each direction change is an edge.

Each cell is represented as 8 vertices. Vertical, horizontal, and diagonal edges are free (cost 0). Others have non-zero cost (or different costs for 45, 90 and 135 degree turns, if you want sharper turns to cost more). Connect adjacent cells in a natural way (N to S, W to E, SW to NE etc). Assign some cost to these edges too (or different costs for vertical/horizontal and diagonal edges, depending on how you define "path length").

Then use A* on the graph. By varying the costs you may tune the balance between "good-looking" and "short".

Upvotes: 2

Hrethric
Hrethric

Reputation: 96

I think you're looking for A* pathfinding. While it will have the side effect of finding the shortest path, it's also going to be natural looking. For a long time it was the gold standard in video games.

Here's an article on the algorithm. Note: you'll have to modify it slightly to allow for diagonal movement.

https://www.raywenderlich.com/4946/introduction-to-a-pathfinding

Upvotes: 2

Related Questions