A star algorithm, but in four directions only

Question

I've been reading about path-finding algorithms and I'm currently looking for one that works just like the A* but where the agent cannot move diagonally. Do the nodes still expand diagonally or is it some other way? Perhaps it's not related to A* at all? Also please consider the following image where it shows that the triangle is our agent, the brown rectangle is an obstacle between the grid squares and the arrow is just to make it clear that you can still walk through squares that have obstacles on their "borders", when not face to face to that obstacle. What kind of algorithm would you advise me as a base to a path-finding problem with these characteristics? Forgive me if something like this was posted already, I couldn't find it.

Answer 1

Just as amit said, A* is a search algorithm and can be applied to (almost) any search problem.

Any search problem can be described (or defined) with these parameters:

• starting state (position)
• transition function (if given any state a, what are states you can get in one step)
• end state (position)

Start and end state as well as transition function can be given explicitly or implicitly, e.g. when moving through a grid (like in your problem), next positions could be any neighbor (up, down, left, right + maybe diagonally) or there could be explicit info contained in one space. End state could also be known before hand (e.g. state with coordinates (x,y)), or it could be defined by some characteristic of the state (e.g. if there are coins in the grid, end state could be any state with a coin).

Most common search algorithms are BFS, DFS, iterative-DFS (non-directed), hill-climbing, A* (directed). There are many others - look at the graphic on the right of the wiki page. Some of them are complete (meaning, an end state will always be found even in an infinite search space if it exists - BFS, A*), while some are not (DFS, hill-climbing). The other categorization is by algorithms optimality. Optimal searches will find the best possible solution, or the best possible path to it (BFS for non-weighted graphs, A*), while with others will find any acceptable solution or any possible path to the solution (BFS in weighted graphs). Usually, there's a trade-off between computational complexity, memory requirements and the simplicity of the implementation. Directed searches additionally use some pre-known information about the end state to direct a search (estimate of the end-state distance from any given state), while non-directed searches do not.

For example, if you know the coordinates of the start and end positions, directed search makes sense. If start position is in the upper left corner, and the end position is in the lower left corner, you prefer to search the states in the downward direction versus the states to the right. If your start position is in the middle of the board, end the end position in not explicit (defined by a characteristic), and can be anywhere in the board, directed search is not of much help.

Also, if your problem is not of great magnitude (e.g. search in a 100x100 board), there usually isn't a good reason to use directed search, BFS or other non-directed search algorithms will work fast enough and the speed-up gained by using more complex, directed searches is not significant.

Notice that all of the search algorithms can work with any given transition function.

So, to conclude. The type of algorithm you should use depends on your problem limitations:

• small search-space, no known info about the end state: un-directed (BFS, DFS)
• limited memory: DFS, iterative-DFS
• larger search-space + known information about the end state: directed (A*, hill-climbing)
• no local extremes in the search space (e.g. no obstacles) or limited memory + known info about the end: hill-climbing
• there usually are many more limitations to be taken into account, and the search algorithms are just examples of algorithms that might be good in said situations (but also might not be, depending on additional limitations)

This is just a short overview of the search algorithms and just gives the general ideal. If you are uncertain about which algorithm is most suitable for your problem, you should read up on the characteristics and applications in more detail.

Hope this helps ;)

Answer 2

A* is a search algorithm in a graph, given a starting location and a set of target nodes, it finds a path - based on the graph's vertices and edges.

If you want your agent to be unable to move diagonally, all you need to do is design your graph such that there is no edge between diagonal vertices.

I assume you are using a next:V->2^V function to get all positions your agent can be next step. If it is the case, just make sure diagonals are not returned from this function.