Algorithm for 'shortest path' with walking agent

user_4693430 0
Viewed 235

I am looking for a shortest path algorithm where the agent (the thing that has to move from start to finish) has only a limited view on the walkable field. Let's say we have a labyrinth with a start and a goal that is tile-based. Something like this: enter image description here The agent then might only be able to see one in each direction (up, down, left, right) but has unlimited memory. As a measurement I want as few steps as possible to reach the goal. Is there an algorithm for that?

And if so is there an algorithm for a more general problem. Let's say: a graph, multiple goals and starts and a function that returns seen nodes, and limited memory?

A solution using a star with total vision: enter image description here

path-finding algorithm
4 Answers

After a while, some ideas and similarities came to my mind.

It is close to the problem that a Micromouse has to solve most use Flood Fill

Flood-fill (node, target-color, replacement-color):
 1. If target-color is equal to replacement-color, return.
 2. ElseIf the color of node is not equal to target-color, return.
 3. Else Set the color of node to replacement-color.
 4. Perform Flood-fill (one step to the south of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
 5. Return.
user_46934300

A very simple alternative approach is:

walk to an undiscovered tile using a star
if it is the goal stop
if not repeat
if there aren't any undiscovered tiles stop and fail
user_146648440

Basically A* will still work but you need to find a new heuristic, i recommend that you include travel time between tiles to do so.

user_148549240

With limited visibility, you can't really expect to find a shortest path because either you can see a path to the goal or you can't, unless you're lucky enough to see multiple paths.

However, you could use a heuristic to improve your search. For example, you'll want to explore unexplored tiles, prioritizing those around your goal, starting with those that are closest. With visibility of only 1, you're basically blind, but if you had slightly higher visibility, you could prioritize exploring around the goal until you find a path that connects to something you've already explored.

This reminds me of bidirectional path tracing, a technique in rendering where you trace paths from both the camera and the light until they connect. http://www.pbr-book.org/3ed-2018/Light_Transport_III_Bidirectional_Methods/Bidirectional_Path_Tracing.html

user_20959530
Related