CODEWITHSUNDEEP
algorithmpath-finding
Xanlantos
Xanlantos

Reputation: 967

Algorithm for 'shortest path' with walking agent

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

Upvotes: 4

Views: 407

Answers (4)

TorAmm
TorAmm

Reputation: 21

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.

Upvotes: 1

Torben Ammelt
Torben Ammelt

Reputation: 33

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

Upvotes: 2

Xanlantos
Xanlantos

Reputation: 967

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.

Upvotes: 2

frodo2975
frodo2975

Reputation: 11725

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

Upvotes: -1

Related Questions