Ground pathfinder enhancement

[lamer]

How about changing/optimizing path-finder algorithm?
Specifically talking about ground unit that can't get past the wall of friendly units.

I'm looking into next algo:
1. Consider friendly standing units (in a "hold position" mode) as blocking tiles, find path1. If path1 contains no blocking units then return path1.
2. Find path2 without units as blockers (as it is now in v3.1).
3. Compare complexity of both paths (use speed+distance+something-else as a metric). If path1 better return path1.
4. Move away blocking units (if they are in no "hold position"). After A* computes path we can move several units from path (not only first blocking as it is now).

Is there a point for such optimization? (Can't estimate if it worth the effort as I'm new to this stuff and only did a quick-look of sources in master)
----
on second thought - no need for path2, just add cost of moving to tiles occupied by unit.
Maybe the major problem would be in tracking unit's position/tile, as one small unit can occupy 4 tiles in worst case.

[vexed]

Hmm, If you feel like implementing it, give it a shot, and we can see how it goes from there.
I do suggest you work on the master codebase though, since there isn't much life left in 3.x.

[lamer]

I'll play with pathfinder in a local branch, but so much homework to do (useful resources, multi-agent pathfinding algorithms):

http://www.aaai.org/Conferences/AAAI/aaai.php

http://www.gamasutra.com/view/feature/1 ... vement.php
http://aigamedev.com/open/tutorial/lazy-theta-star/

http://citeseerx.ist.psu.edu/viewdoc/do ... 1&type=pdf
http://ijcai.org/papers11/Papers/IJCAI11-117.pdf
http://trevorstandley.appspot.com/Korf_Project.pdf
http://movingai.com/mapf/slides/roeger-helmert.pdf
http://www.cs.rutgers.edu/~kb572/pubs/p ... _ijcai.pdf
http://webdocs.cs.ualberta.ca/~holte/Pu ... iagent.pdf
http://users.cecs.anu.edu.au/~cwang/icaps08-paper.pdf
http://abotea.rsise.anu.edu.au/data/wan ... ecai10.pdf
http://www.jair.org/media/3370/live-3370-5850-jair.pdf
http://ijcai.org/papers09/Papers/IJCAI09-310.pdf

http://code.google.com/p/recastnavigation/
http://digestingduck.blogspot.com/
http://opensteer.sourceforge.net/
http://gamma.cs.unc.edu/CA/ClearPath.pdf

So don't expect fast (or any) results from me

[lamer]

Got some results. Not perfect but does what i want from it (need more testing though ). Also read about ClearPath, ORCA, Crowd flows, etc and maybe will try to implement some of it later when i have time.

But for now.. how can i share my code? Create another git repo? I did all changes in separate local branch.

[vexed]

Got some results. Not perfect but does what i want from it (need more testing though ). Also read about ClearPath, ORCA, Crowd flows, etc and maybe will try to implement some of it later when i have time.

But for now.. how can i share my code? Create another git repo? I did all changes in separate local branch.

Yes please, on github would be best, then you can push your work there. Just make an account, and go to https://github.com/Warzone2100/warzone2100 and click the fork button.

[lamer]

Never forked any project earlier, thus don't know what information needs to be provided.
Forked repo - https://github.com/rlcevg/warzone2100.git
master contains all changes but previous commit 7c3657edab8 contains additional visual debug info.
CHANGES: Unit that is ordered to move will try to avoid standing units during path planning stage (A*).

[Per]

That looks interesting!

[lamer]

Some final notes (just have a lack of experience and interest).
No need for monster ORCA (local collision avoidance). Present algorithm (in moveGetObstacleVector) seems fast enough and works really nice with small group of units. But it counts only obstacles in front and no backward velocities allowed. Thus stuck in a row of units.
Next stage is shuffle (as collision resolver i guess). Stuck-unit pushes one unit in front (180 deg). That pushes another one etc, etc. With lots of big units in a packed group they just have no time to move as moveReachedWayPoint calms them down really fast. With increase of move-away distance (in moveShuffleDroid) or increase of calm-down time (in moveReachedWayPoint) units just keep dancing around.
Maybe some kind of priority system should be involved and/or calm-down time based on unit's radius/speed. Couldn't find quick fix for that (maybe collision resolver should be rebuilt). And because avoidance during path planning (and thus during replanning if droid stuck) works i'll stop at this point.
Avoidance during A* has its drawback: long path when short one is free after planning, but it looks like unit choose alternative path. Works for me

[vexed]

Some final notes (just have a lack of experience and interest).
No need for monster ORCA (local collision avoidance). Present algorithm (in moveGetObstacleVector) seems fast enough and works really nice with small group of units. But it counts only obstacles in front and no backward velocities allowed. Thus stuck in a row of units.
Next stage is shuffle (as collision resolver i guess). Stuck-unit pushes one unit in front (180 deg). That pushes another one etc, etc. With lots of big units in a packed group they just have no time to move as moveReachedWayPoint calms them down really fast. With increase of move-away distance (in moveShuffleDroid) or increase of calm-down time (in moveReachedWayPoint) units just keep dancing around.
Maybe some kind of priority system should be involved and/or calm-down time based on unit's radius/speed. Couldn't find quick fix for that (maybe collision resolver should be rebuilt). And because avoidance during path planning (and thus during replanning if droid stuck) works i'll stop at this point.
Avoidance during A* has its drawback: long path when short one is free after planning, but it looks like unit choose alternative path. Works for me

I did a quick test of the changes, using map Rush, advanced bases. (two different teams, red & blue, so I could see what they were doing)
Made 30 units inside the base, and 30 other units outside, and told the inside ones to go out, and the outside ones to go in, and... they still jammed up.

[lamer]

It's good to know the criteria. Actually avoidance of standing units was sufficient for me.
Will try to implement "Push and swap"(http://www.cs.rutgers.edu/~kb572/pubs/p ... _ijcai.pdf) later. Yet i have doubts how to do it for units with different size.
Any advise or guidance appreciated.