POV-Ray : Newsgroups : povray.programming : Help minimizing pre-processing graphic for A* pathfinding Server Time
18 Jul 2024 06:46:29 EDT (-0400)
  Help minimizing pre-processing graphic for A* pathfinding (Message 1 to 6 of 6)  
From: Bald Eagle
Subject: Help minimizing pre-processing graphic for A* pathfinding
Date: 20 Apr 2024 17:30:00
Message: <web.66243367a935d2a61f9dae3025979125@news.povray.org>
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".

The real issue I'd like to solve is that A* didn't care that the shortest path
involved exiting the building and then coming back in.  That likely violates
policy, and plus the doors are exit-only (panic bar on the inside only).

At present, I'm just using image pixel color to define where empty space or a
door is, and everything else is solid object.  (the SDL currently draws over
anything it determines as solid - regardless of the color on the map -  with a
bright green, as a means evaluating the quality of the image colors & evaluation
logic)
Also, as you can see, the color logic is cumbersome and finicky - dark red
pallets get evaluated as "doors" (walkable space) and very dark grey doesn't
register as solid (because my logic sucks that bad)

#if (((PixelColor.red + PixelColor.green + PixelColor.blue)/3 < 0.9) &
(PixelColor.red < 0.85 & (PixelColor.green + PixelColor.blue)/2 > 0.05))

#declare walkability [X][Y] = unwalkable;

I'd like:
1. A clear manner of coding a door as being one-way.  Keep in mind that the door
in the graphic may be many pixels wide/deep, and there's no color
differentiation between inside and outside.

2. I'd like a general solution, but also one that minimizes the amount of
additional work to be done before running the pathfinding from the start point
to the destination (designated meeting place)

3. Any ideas on how to minimize the search time, even though they might cost
more initial work are welcome.  The idea is to run simulations when there may be
obstacles blocking the typical posted primary fire exit path.

I've been thinking of color coding, specifying a door <x, y> coupled with a
directional vector (I currently have 22 doors), using Crossing Numbers, Voronoi,
etc.

Also of interest is finding fire extinguishers, first aid kits, and AED
defibrillators.

With regard to fire extinguishers, I asked the question: what if I need one, but
someone has already taken it?  What direction do I go to get the next closest
one?  Or the third?

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

- BW


Post a reply to this message


Attachments:
Download 'a-star floorplan exits.png' (403 KB)

Preview of image 'a-star floorplan exits.png'
a-star floorplan exits.png


 

From: ingo
Subject: Re: Help minimizing pre-processing graphic for A* pathfinding
Date: 21 Apr 2024 01:55:00
Message: <web.6624a90be0fc61c517bac71e8ffb8ce3@news.povray.org>
"Bald Eagle" <cre### [at] netscapenet> wrote:

>
> 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".
>

The print factory where I worked (solvent based rotogravure printing) was
sectioned. Huge safety doors would close of sections in case of emergency.
People would try to outrun the closing of these doors, the building is 250 m
long with 5 sections. Not a situation you want.

To get proper routes out we added more outside gathering points for
people(counting). Maybe adding an extra gathering point (green dot?) on the
other side of the building works?


ingo


Post a reply to this message

From: Bald Eagle
Subject: Re: Help minimizing pre-processing graphic for A* pathfinding
Date: 21 Apr 2024 08:45:00
Message: <web.66250a02e0fc61c51f9dae3025979125@news.povray.org>
"ingo" <nomail@nomail> wrote:

> The print factory where I worked (solvent based rotogravure printing) was
> sectioned. Huge safety doors would close of sections in case of emergency.
> People would try to outrun the closing of these doors, the building is 250 m
> long with 5 sections. Not a situation you want.

Jeez.  Sounds like that scene from Moonraker.

> To get proper routes out we added more outside gathering points for
> people(counting). Maybe adding an extra gathering point (green dot?) on the
> other side of the building works?

I was just trying to make the solver take as long and convoluted path as I
could, and the algorithm that I have now only takes a start and target point as
input.
I think I can sequentially solve for different paths and store those in
different path number array, but at the present time, that's about it.

I was just trying to conceptually figure out how to code a 1-way door

After that, I figured some thing to try might be:
  solve a single designated path
  solve multiple single paths
  solve a progressive path with sequential destination points
  solve a single path then repeat using a given obstacle
  find the closest destination of many to a given starting point

But mostly I was just thinking that I might have to use different versions of
the map, or someone might want me to test this on another site, and I wanted to
minimize the amount of work I might need to do to start having the algorithm do
its thing.

I tried loading yesbird's povlab website to see if I could use that to speed up
the parsing, but it's in a "forbidden country"   <eyeroll>

- BE


Post a reply to this message

From: yesbird
Subject: Re: Help minimizing pre-processing graphic for A* pathfinding
Date: 21 Apr 2024 16:33:45
Message: <66257829$1@news.povray.org>
On 21/04/2024 15:43, Bald Eagle wrote:
> I tried loading yesbird's povlab website to see if I could use that to speed up
> the parsing, but it's in a "forbidden country"   <eyeroll>

Yes, guys, sad, but true. Last two years I'm living in "forbidden
country", trying to suppress this unpleasant fact. But "open source" is
always open and free, so if you have hardware resources, you can use my
code to make the same service in any "unforbidden" country:
https://github.com/syanenko/povlab.online
--
YB


Post a reply to this message

From: yesbird
Subject: Re: Help minimizing pre-processing graphic for A* pathfinding
Date: 21 Apr 2024 17:17:07
Message: <66258253$1@news.povray.org>
On 21/04/2024 15:43, Bald Eagle wrote:
> I tried loading yesbird's povlab website to see if I could use that to speed up
> the parsing, but it's in a "forbidden country"   <eyeroll>

... or try VPN.


Post a reply to this message

From: Le Forgeron
Subject: Re: Help minimizing pre-processing graphic for A* pathfinding
Date: 23 May 2024 14:29:02
Message: <664f8aee$1@news.povray.org>
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

Copyright 2003-2023 Persistence of Vision Raytracer Pty. Ltd.