Path Finding
- Terminator
- Regular
- Posts: 1077
- Joined: 05 Aug 2006, 13:46
- Location: Ukraine
- Contact:
Path Finding
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 ?)
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
Russian-speaking Social network Group http://vk.com/warzone2100
Re: Path Finding
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."
- Rman Virgil
- Professional
- Posts: 3812
- Joined: 25 Sep 2006, 01:06
- Location: USA
Re: Path Finding
--------->
* 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
* 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
.
Impact = C x (R + E + A + T + E)
Contrast
Reach
Exposure
Articulation
Trust
Echo
.
- Terminator
- Regular
- Posts: 1077
- Joined: 05 Aug 2006, 13:46
- Location: Ukraine
- Contact:
Re: Path Finding
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
Russian-speaking Social network Group http://vk.com/warzone2100
- Rman Virgil
- Professional
- Posts: 3812
- Joined: 25 Sep 2006, 01:06
- Location: USA
Re: Path Finding
* that's interstin.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....
* 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
.
Impact = C x (R + E + A + T + E)
Contrast
Reach
Exposure
Articulation
Trust
Echo
.
- Terminator
- Regular
- Posts: 1077
- Joined: 05 Aug 2006, 13:46
- Location: Ukraine
- Contact:
Re: Path Finding
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
Russian-speaking Social network Group http://vk.com/warzone2100
Re: Path Finding
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."
Re: Path Finding
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.
- 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.
- Terminator
- Regular
- Posts: 1077
- Joined: 05 Aug 2006, 13:46
- Location: Ukraine
- Contact:
Re: Path Finding
yes this is that What I wanted to tell. Seems like they units dont see too long forward just what they have under their fitsPer wrote: There has been some code changes in the obstacle avoidance code, perhaps related to the problems you see?
Death is the only way out... sh*t Happens !
Russian-speaking Social network Group http://vk.com/warzone2100
Russian-speaking Social network Group http://vk.com/warzone2100
- Rman Virgil
- Professional
- Posts: 3812
- Joined: 25 Sep 2006, 01:06
- Location: USA
Re: Path Finding
------>
* I wonder what the difference is between "Path Finding Code" and "Obstacle Avoidance Code"... ?
* Maybe it's like "Sunrise" and "Sunset" ?
- RV
* 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
.
Impact = C x (R + E + A + T + E)
Contrast
Reach
Exposure
Articulation
Trust
Echo
.
- Terminator
- Regular
- Posts: 1077
- Joined: 05 Aug 2006, 13:46
- Location: Ukraine
- Contact:
Re: Path Finding
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
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 (6.58 KiB) Viewed 6898 times
Death is the only way out... sh*t Happens !
Russian-speaking Social network Group http://vk.com/warzone2100
Russian-speaking Social network Group http://vk.com/warzone2100
Re: Path Finding
Pathfinding is not that trivial.
We all have the same heaven, but not the same horizon.
Re: Path Finding
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).
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.
Re: Path Finding
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?
Re: Path Finding
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.
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.