a general path-finding question

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

a general path-finding question

gershon
I'm using the A* algorithm as implemented in the aPath library on haxelib, it does a good job and works well.

my question is regrading continuous updating of the target, when calculating the path, visited  nodes are marked closed, so backing-up the path usually leaves you when very little or none at all adjacent nodes to travel too,
which usually causes the engine to fail calculating a new path, and because of the way i wired it all up, i get thrown a null and the pathfinding stops...

that was just one example of why pathfinding fails, there are other reasons, and for now the only way i found to get around it is to totally regenerate the map, which is the the single most expensive (time-wise) thing to do...

there's this link, which is the most comprehensive A* resource i've seen, but as this list is populated with so many game-programmers, i thought i'll ask here...

10x, gershon.

 

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: a general path-finding question

edA-qa mort-ora-y
gershon wrote:
> my question is regrading continuous updating of the target, when
> calculating the path, visited  nodes are marked closed, so backing-up
> the path usually leaves you when very little or none at all adjacent
> nodes to travel too,

Perhaps if you explain what your are trying to do I can help you find
the write variation of a path finding algorithm to use.

I'm guessing that if you are doing something where objects continually
move you only have two options:
1) Continually recalculate
2) Use an iterative algorithm

You've already said #1 is too slow, but depending on what you're doing
there are ways to calculate this quicker.  For example, you can separate
between micro and macro paths (levels of detail).

Number 2 is suited when you need a continuous fine detail.  Usually here
you can do iterative passes from the target.  Starting at the target
simply count backwards through the grid -- applying conditions as you
go.  On each iteration you recalculate the whole grid (or a large part).
  This recalc however is very quick, doesn't deal with node lists or
anything -- it is a one pass on every cell to figure out the direction
to the target.

I'm guessing games like the popular Tower Defence are using a variation
on this method -- you can tell as the insects take a while to respond to
a blocked path.

--
edA-qa mort-ora-y
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

BigTPoker uses haXe and DHLIB
        http://BigTPoker.com/?source=haxe-list

The dis-Emi-A haXe Library
        http://wiki.disemia.com/HaXe
       
A full set of tools, classes, and support facilities aimed at
simplifying and expediting game creation in Flash 9.

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Sign: Please digitally sign your emails.
Encrypt: I'm also happy to receive encrypted mail.


--
haXe - an open source web programming language
http://haxe.org

signature.asc (260 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: a general path-finding question

jlm@justinfront.net
In reply to this post by gershon
No games expert, but my nieve approach might be...
I would have thought that if a child updates a binary in its parent,  
'childrenVisitCount' then you can check the binary value with the  
total children next time you pass through.  If you need to sometimes  
clear the paths then you can use a static method that loops through  
all instances (which are stored as a list on the class when instances  
created) to initialise the 'childrenVisitCount'.


On 27 Jul 2009, at 11:25, gershon wrote:

> a new path, and because of the way i wired it all up, i get thrown a  
> null and the pathfinding stops...
>
> that was just one example of why pathfinding fails, there are other  
> reasons, and for now the only way i found to get around it is to  
> totally regenerate the map, which is the the single most expensive  
> (time-wise) thing to do...


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: a general path-finding question

jlm@justinfront.net
Actually each child would need a depth level so it would add itself in  
the right place of the binary number  1011 + the second child = 1111.
On 27 Jul 2009, at 12:03, Justin Lawerance Mills wrote:

> No games expert, but my nieve approach might be...
> I would have thought that if a child updates a binary in its parent,  
> 'childrenVisitCount' then you can check the binary value with the  
> total children next time you pass through.  If you need to sometimes  
> clear the paths then you can use a static method that loops through  
> all instances (which are stored as a list on the class when  
> instances created) to initialise the 'childrenVisitCount'.
>
>
> On 27 Jul 2009, at 11:25, gershon wrote:
>
>> a new path, and because of the way i wired it all up, i get thrown  
>> a null and the pathfinding stops...
>>
>> that was just one example of why pathfinding fails, there are other  
>> reasons, and for now the only way i found to get around it is to  
>> totally regenerate the map, which is the the single most expensive  
>> (time-wise) thing to do...
>
>
> --
> haXe - an open source web programming language
> http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: a general path-finding question

gershon
Appericate the quick respone :)

I've upped a demo here, to better explain myself.

Sliders, Steppers and ProgressBars have little circles to the left which i call Sockets, by clicking and "dragging" you should see a path start to form which i call Patch, because it should act like a patch-cable to connect sockets... (those two classes are in the "toys" package)

you can use ctrl-click on a widget to translate\scale it, and you can open the console and change the grid spacing with "Haxegui.gridSpacing" (mind the case).

If you're using the debug player, you'll be shown an alert, if not the path just stops.

Another weird behavior is  that dragging really fast actually almost works...


On Mon, Jul 27, 2009 at 2:21 PM, Justin Lawerance Mills <[hidden email]> wrote:
Actually each child would need a depth level so it would add itself in the right place of the binary number  1011 + the second child = 1111.

On 27 Jul 2009, at 12:03, Justin Lawerance Mills wrote:

No games expert, but my nieve approach might be...
I would have thought that if a child updates a binary in its parent, 'childrenVisitCount' then you can check the binary value with the total children next time you pass through.  If you need to sometimes clear the paths then you can use a static method that loops through all instances (which are stored as a list on the class when instances created) to initialise the 'childrenVisitCount'.


On 27 Jul 2009, at 11:25, gershon wrote:

a new path, and because of the way i wired it all up, i get thrown a null and the pathfinding stops...

that was just one example of why pathfinding fails, there are other reasons, and for now the only way i found to get around it is to totally regenerate the map, which is the the single most expensive (time-wise) thing to do...


--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: a general path-finding question

edA-qa mort-ora-y
gershon wrote:
> Sliders, Steppers and ProgressBars have little circles to the left which
> i call Sockets, by clicking and "dragging" you should see a path start
> to form which i call Patch, because it should act like a patch-cable to
> connect sockets... (those two classes are in the "toys" package)

You shouldn't have a problem doing A* on every motion of the mouse to a
new grid location.  You aren't doing that many calculations that you
should have a speed problem.  Just make sure you only recalculate when
going to a new grid location with the mouse.

If it is going too slow perhaps your code just needs a bit of cleaning
up -- reduce allocations, use a different vector/list class.

Make sure your heuristic function is good as well. In your case simply
the x+y length is likely good enough (or diagonally length if you can go
diagonally).


--
edA-qa mort-ora-y
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

BigTPoker uses haXe and DHLIB
        http://BigTPoker.com/?source=haxe-list

The dis-Emi-A haXe Library
        http://wiki.disemia.com/HaXe
       
A full set of tools, classes, and support facilities aimed at
simplifying and expediting game creation in Flash 9.

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Sign: Please digitally sign your emails.
Encrypt: I'm also happy to receive encrypted mail.


--
haXe - an open source web programming language
http://haxe.org

signature.asc (260 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: a general path-finding question

gershon
The aPath class is a standard implementation of a*, uses both x\y and diagonal distances for the heuristic, and is quite fast.
I'll try and optimize the best i can (maybe use powers of 2 and bitwise operations for the grid, and maybe a haxe FastList can speed up the open\closed list...)

The map generation on the other hand is very slow, it currently iterates all the cells and checks whats under the center of the cell (like raycasting in the z-axis), on top of that, unless the widgets are snapped to grid (default is not) or the grid resolution is too low, mapping is bad.

one solution i have is to do multi-sampling per-cell, which slows the generation even more, guess i have to find a trade-off between grid size and number of samples...
basically, there's no need to regenerate the map while pathfinding, as everything is static.
I'd like to  do a "high-quality" mapping on startup, "low-quality" on any redraw, and some kind of refinement before\while pathfinding...

the engine is "dumb", it only solves paths, or it doesn't. 

so, i've put the solving function into a try\catch block, and i'm trying to give it some kind of path-memory, probably a queue sorted by path length, so there'll at least be something close to target, then probably visualize the straight path to the target a little diffrently to let to user know...

sorry for the prolonged rambling, but it helps to write things down ;)

how's the demo btw? did you like the new 7segment widget? its all code, no font used, also working on knobs and such...


On Mon, Jul 27, 2009 at 8:19 PM, edA-qa mort-ora-y <[hidden email]> wrote:
gershon wrote:
> Sliders, Steppers and ProgressBars have little circles to the left which
> i call Sockets, by clicking and "dragging" you should see a path start
> to form which i call Patch, because it should act like a patch-cable to
> connect sockets... (those two classes are in the "toys" package)

You shouldn't have a problem doing A* on every motion of the mouse to a
new grid location.  You aren't doing that many calculations that you
should have a speed problem.  Just make sure you only recalculate when
going to a new grid location with the mouse.

If it is going too slow perhaps your code just needs a bit of cleaning
up -- reduce allocations, use a different vector/list class.

Make sure your heuristic function is good as well. In your case simply
the x+y length is likely good enough (or diagonally length if you can go
diagonally).


--
edA-qa mort-ora-y
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

BigTPoker uses haXe and DHLIB
       http://BigTPoker.com/?source=haxe-list

The dis-Emi-A haXe Library
       http://wiki.disemia.com/HaXe

A full set of tools, classes, and support facilities aimed at
simplifying and expediting game creation in Flash 9.

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Sign: Please digitally sign your emails.
Encrypt: I'm also happy to receive encrypted mail.


--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: a general path-finding question

edA-qa mort-ora-y
gershon wrote:
> I'll try and optimize the best i can (maybe use powers of 2 and bitwise
> operations for the grid, and maybe a haxe FastList can speed up the
> open\closed list...)

If I think about it, an A* search is very closely related to a seedfill
algorithm.  In DHLIB I have a highly optimized seedfill algorithm.
There are lots of little things I did to speed it up, perhaps some of
them can help you.


I didn't look too much at the rest of the demo. Though it looks pretty.

--
edA-qa mort-ora-y
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

BigTPoker uses haXe and DHLIB
        http://BigTPoker.com/?source=haxe-list

The dis-Emi-A haXe Library
        http://wiki.disemia.com/HaXe
       
A full set of tools, classes, and support facilities aimed at
simplifying and expediting game creation in Flash 9.

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Sign: Please digitally sign your emails.
Encrypt: I'm also happy to receive encrypted mail.


--
haXe - an open source web programming language
http://haxe.org

signature.asc (260 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: a general path-finding question

Simon Krajewski
In reply to this post by gershon
gershon schrieb:

> The aPath class is a standard implementation of a*, uses both x\y and
> diagonal distances for the heuristic, and is quite fast.
> I'll try and optimize the best i can (maybe use powers of 2 and
> bitwise operations for the grid, and maybe a haxe FastList can speed
> up the open\closed list...)
>
> The map generation on the other hand is very slow, it currently
> iterates all the cells and checks whats under the center of the cell
> (like raycasting in the z-axis), on top of that, unless the widgets
> are snapped to grid (default is not) or the grid resolution is too
> low, mapping is bad.
This is pretty easy if you're willing to store a little more information:
1. store each object's (by that I mean all these widgets) previous
bounds (in coordinates of the grid)
2. store some kind of reference counter for each grid cell (a two
dimensional int array initialized to 0)

Then listen for all kinds of move, add and remove events, i.e. all
events that might actually change your map. Whenever that occurs, take
the object that caused it and do the following:
1. iterate over it's previous bounds, adding -1 to the reference counter
of each grid cell you pass (unless it's an add event)
2. iterate over it's new bounds, adding 1 to the reference counter of
each grid cell you pass (unless it's a remove event)
3. store new bounds as previous bounds (unless it's a remove event)

Then, all cells with a reference counter > 0 are occupied, all other
cells are free. This is really cheap because you only have to convert
some bounding coordinates into grid coordinates and loop over them,
doing simple add operations in the loop bodies. Converting from "real"
coordinates to the grid coordinates is a simple division by the grid
width/height. Alltogether, if you manage to grab the events properly,
this is a matter of ~10 lines of code.

The reference counting is done because it's possible that when an object
leaves a grid cell, that grid cell is still occupied by a different object.

Regards
Simon

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: a general path-finding question

Gamehaxe
In reply to this post by edA-qa mort-ora-y
Sorry if I miss all this, but could you reverse the problem?
ie, calculate the path from the target to the mouse,
rather then the other way around, since you would not need
to recalculate if the target does not move.

Hugh

> gershon wrote:
>> Sliders, Steppers and ProgressBars have little circles to the left which
>> i call Sockets, by clicking and "dragging" you should see a path start
>> to form which i call Patch, because it should act like a patch-cable to
>> connect sockets... (those two classes are in the "toys" package)
>
> You shouldn't have a problem doing A* on every motion of the mouse to a
> new grid location.  You aren't doing that many calculations that you
> should have a speed problem.  Just make sure you only recalculate when
> going to a new grid location with the mouse.
>
> If it is going too slow perhaps your code just needs a bit of cleaning
> up -- reduce allocations, use a different vector/list class.
>
> Make sure your heuristic function is good as well. In your case simply
> the x+y length is likely good enough (or diagonally length if you can go
> diagonally).
>
>



--
haXe - an open source web programming language
http://haxe.org