Le 20/04/2024 à 23:28, Bald Eagle a écrit :
> Hi folks,
> 
> Been busy and so, many things have stalled.
> 
> We've just had the concrete floors resurfaced - it looks like they've been
> ground down to fresh, clean concrete, and are likely to be sealed in the near
> future.
> 
> I had talked with the VP a while back about painting various lines on the floor,
> and I figured we could paint arrows in the direction of the nearest emergency
> exit.
> 
> So I ran A* on a simple map of the warehouse, and it does OK.
> It does take longer than I'd like to scan the image and generate the arrays of
> walkable vs non-walkable pixels, and then again to solve the "maze".
> 

> 
> I'd welcome any ideas, or even questions that help me avoid future unseen
> pitfalls.
> 
> - BW
> 

Can you consider as "Now safe" when reaching an external door, even if 
still far from the meeting point ?

If yes, I would set each external door a node of cost 0.
All nodes which are outside also get a cost of 0.
Other nodes start with unknown cost.

Ideally the grid of connections between nodes is your green/white picture.

Then just let diffuse the increasing cost by looping over each node:
- if cost is known, nothing to do
- if cost is still unknown, scan the neighbour nodes (taking the 
connection's map into account) for any known Cost, K=1+min(known cost of 
reachable neighbour).
- - if there is a know cost for at least one neighbour, set the cost of 
node to K
- - otherwise, ignore that node for this iteration.

Repeat as long as at least one node has been given a cost during iteration.

You might have different result according to the grid of nodes
- looking E,W,N,S only
- looking E,W,N,S but also NE,SE,NW,SW
- using hex-grid instead of square-grid (also 6 or 12 directions for 
neighbours)

Once you have finished the cost of every point, you can visualize it as 
a heightfield. (if your nodes are on a square grid) (I would recommend 
making "unknown cost" node at 0,
and adding a significant offset to the known cost, possibly with linear 
interpolation if the max cost get bigger than 65535-offset)


Why I did not use A* : because you are looking for the gradient of every 
point toward any exit, not routing a robot from A to B.
And the result is static.
So, it's the return of Dijkstra and diffusion of cost on a grid.

Notice that you can implement it with a "last updated node queue", but 
you would need to first replace the whole grid with a collection of 
nodes which hold coordinates of each allowed neighbour, but it is 
trading memory and precomputation of connections against simplicity of 
looping over a big array again and again.

Post a reply to this message