Path Finding

Warzone 2.1.x series. (Unsupported--read only!)
User avatar
Terminator
Regular
Regular
Posts: 1077
Joined: 05 Aug 2006, 13:46
Location: Ukraine
Contact:

Path Finding

Post by Terminator »

Tryed to find in wiki about Current PF system but there is only in roadmap & what its must like to be.

I wanted to ask about Current( in 2.1) PF Where Can I find info about it or Tel here in few words. I'm asking because 2.1 becoming more stable & playable & this PF a little annoying me after 3-5 games. (Seems like in 2.0.x PF was different or i'm wrong ?)
Death is the only way out... sh*t Happens !

Russian-speaking Social network Group http://vk.com/warzone2100
Per
Warzone 2100 Team Member
Warzone 2100 Team Member
Posts: 3780
Joined: 03 Aug 2006, 19:39

Re: Path Finding

Post by Per »

Path finding code has not been changed since the original game.
"Make a man a fire, you keep him warm for a day. Set a man on fire, you keep him warm for the rest of his life."
User avatar
Rman Virgil
Professional
Professional
Posts: 3812
Joined: 25 Sep 2006, 01:06
Location: USA

Re: Path Finding

Post by Rman Virgil »

--------->

* Yep, WZ's PF sux.

* The schema is called "A*".

* The beauty though is that it can be made far better by integrating PF "HPA*"... and you don't have to chuck pre-existing "A*".

* Specific to the SKI A.I. would be "Tile Iteration".

* Anyhow, that's a HO. Could be misguided. ;)

- RV :)
.

Impact = C x (R + E + A + T + E)

Contrast
Reach
Exposure
Articulation
Trust
Echo
.
User avatar
Terminator
Regular
Regular
Posts: 1077
Joined: 05 Aug 2006, 13:46
Location: Ukraine
Contact:

Re: Path Finding

Post by Terminator »

So I still dont understand Why comparing Unit's moves  from 2.0.x & 2.1 - is different ? In 2.1 - Untis Become more "stupid" ? & moves make units like  Driveing on the Ice all the time....
Death is the only way out... sh*t Happens !

Russian-speaking Social network Group http://vk.com/warzone2100
User avatar
Rman Virgil
Professional
Professional
Posts: 3812
Joined: 25 Sep 2006, 01:06
Location: USA

Re: Path Finding

Post by Rman Virgil »

Terminator wrote: So I still dont understand Why comparing Unit's moves  from 2.0.x & 2.1 - is different ? In 2.1 - Untis Become more "stupid" ? & moves make units like  Driveing on the Ice all the time....
* that's interstin.

* when you say "like driving on ice" you mean tanks, right ?

* Let me ask you this:

* Have you noticed Cyborgs legs moving but they are not walking anywhere ?

* Or how about VTOLs - have you noticed them all of a sudden "Stall" in mid-flight, not moving ?

* You playing on 8-Player Maps ?

- RV :)
.

Impact = C x (R + E + A + T + E)

Contrast
Reach
Exposure
Articulation
Trust
Echo
.
User avatar
Terminator
Regular
Regular
Posts: 1077
Joined: 05 Aug 2006, 13:46
Location: Ukraine
Contact:

Re: Path Finding

Post by Terminator »

no I dont mean that... :(  I mean that Units get in trap (situations where they need help in find a wayout) more often than it was befor.
Death is the only way out... sh*t Happens !

Russian-speaking Social network Group http://vk.com/warzone2100
Per
Warzone 2100 Team Member
Warzone 2100 Team Member
Posts: 3780
Joined: 03 Aug 2006, 19:39

Re: Path Finding

Post by Per »

There has been some code changes in the obstacle avoidance code, perhaps related to the problems you see? The only time I see units "driving on ice" is when they are stuck against obstacles in the terrain.
"Make a man a fire, you keep him warm for a day. Set a man on fire, you keep him warm for the rest of his life."
ratarf
Trained
Trained
Posts: 154
Joined: 29 Nov 2006, 09:45

Re: Path Finding

Post by ratarf »

We noticed the pathfinding problem too while testing in a LAN. There were 2 main problems:

- More often than before, units at the tail of a group will take a different way than the first units. Maybe this could be prevented by using the current location of the first units as a waypoint for the tail units (I don't have a clue if this make any sense)
- It's REALLY hard to force units through small openings. I'm very sure this is different than in other versions of warzone.
User avatar
Terminator
Regular
Regular
Posts: 1077
Joined: 05 Aug 2006, 13:46
Location: Ukraine
Contact:

Re: Path Finding

Post by Terminator »

Per wrote: There has been some code changes in the obstacle avoidance code, perhaps related to the problems you see?
yes this is that What I wanted to tell. Seems like they units dont see too long forward just what they have under their fits
Death is the only way out... sh*t Happens !

Russian-speaking Social network Group http://vk.com/warzone2100
User avatar
Rman Virgil
Professional
Professional
Posts: 3812
Joined: 25 Sep 2006, 01:06
Location: USA

Re: Path Finding

Post by Rman Virgil »

------>

* I wonder what the difference is between "Path Finding Code" and "Obstacle Avoidance Code"... ?

* Maybe it's like "Sunrise" and "Sunset" ?

- RV ;)
.

Impact = C x (R + E + A + T + E)

Contrast
Reach
Exposure
Articulation
Trust
Echo
.
User avatar
Terminator
Regular
Regular
Posts: 1077
Joined: 05 Aug 2006, 13:46
Location: Ukraine
Contact:

Re: Path Finding

Post by Terminator »

So here is pic that Often happens in 2.1

You(devs) should to make Units to "think" forward more deaper. I mean to make calculations on few steps forward & only than make a move
Attachments
post.png
post.png (6.58 KiB) Viewed 6898 times
Death is the only way out... sh*t Happens !

Russian-speaking Social network Group http://vk.com/warzone2100
Kamaze
Regular
Regular
Posts: 1017
Joined: 30 Jul 2006, 15:23

Re: Path Finding

Post by Kamaze »

Pathfinding is not that trivial.
We all have the same heaven, but not the same horizon.
Chojun
Regular
Regular
Posts: 518
Joined: 25 Nov 2006, 17:49
Contact:

Re: Path Finding

Post by Chojun »

Warzone uses A* coupled with a custom gateway implementation to get units from point A to point B.

A* is a tried and true algorithm (complete) and if implemented correctly, will ALWAYS (without exception) get units to where they need to go (unless that location is impassible).

Gateways are an optimization for the A* algorithm and accomplishes a similar technique as the HPA* algorithm.

However, units will undergo special handling in the code if they collide with anything, whether it is a structure, unit, terrain, feature, etc.  In short, this is by moving back and forth until whatever is in the way is cleared.  Groups of stationary units will be "bumped" out of the way if a unit is trying to move through them (meaning, in the code they are issued a command to "move a little bit").

Collision avoidance is not activated if hostile units meet.  Although this may seem logical, in many cases it is a problem in-and-of-itself (e.g. retreating unit stuck up against an enemy unit dies).

Warzone has a problem when there are many units on the battlefield.  Raising the unit cap beyond 100 surely has significantly compounded this problem.   >:(

Warzone will only process a certain amount of pathfinding-related instructions per "frame".  If a unit is stuck in the air or doesn't move for a long time, it is because there are too many units on the field and Warzone can't keep up with the new orders/waypoints being issued.

The issue of trucks spinning around in circles only occurs when the truck is near damaged structures (requiring you to baby-sit them).  I believe this is related to truck-specific AI and has nothing to do with pathfinding.  VTOLs circling around the landing pad is also a VTOL-specific issue.

Here are a few things you can do:

If you ever encounter stuck (frozen) units then try doing the "get off my land" cheat or use the debug mapping to kill all enemy units.  This should fix the issue.  If it does, please post here.

If a truck is spinning around, get another truck to repair the damaged buildings nearby.  The truck should stop spinning.

There are a few things that people should understand:

If there is ONE unit on the map, and you can't get that unit to go from any point A to any other point B, then it is a problem with the A* algorithm.  This is, by definition, a "pathfinding" issue.

Any other issue is a pathfinding ENGINE issue, collision-detection issue, or cognitive/heuristic-AI issues.  There is an important distinction here, as pathfinding (the ability to find a path) really doesn't get better than A* (Dijkstra's shortest-path Algorithm).
The best thing to do when your philosophies don't stand up to debate is to lock the thread and claim victory.
User avatar
Verminus
Trained
Trained
Posts: 121
Joined: 18 Feb 2008, 19:13
Location: Peterborough, England
Contact:

Re: Path Finding

Post by Verminus »

quick question, where does "Stupid tank driver trying to drive up impassable cliff when the end of the cliff is 2 tiles away" fit in?
Kamaze
Regular
Regular
Posts: 1017
Joined: 30 Jul 2006, 15:23

Re: Path Finding

Post by Kamaze »

Don't say something about Dijkstra, i wrote a exam about it yesterday...
However, the only thing which could solve some Pathfinding-Related issues, is more Pre-Processing and eliminating of calculations.
I thought about it a little, and my ideas are (without knowing how warzone handles pathfinding) to implement (i can't do it...) a "bump" area about units, this means that they keep a larger distance to each other, so that they can make some free room when another unit wants to pass. However, this would imply a mass-bumping... And about mass-movement, means when more than one unit is selected, the path can maybe calculated once and the unit on the top becomes the "leader" all others just follow this leader.
We all have the same heaven, but not the same horizon.
Locked