Pathfinding Showcase

[Jeru]

<a href="/0ad/images/news_images/pathfind-terrain3.jpg"><img src="/0ad/images/news_images/pathfind-terrain3-thumb.jpg" width="400" height="300"></a>

Check out this new screenshot visualizing the improved pathfinding system, now featuring naval movement on water and land units wading through shallows.

The spearman on the right has been told to walk over to the left. Red tiles (deep water, steep slopes and buildings) have to be avoided. The green/blue/grey tiles are the extent of the pathfinder's search, before it discovers that the path through the shallows (indicated by the white line/squares) is the quickest way to the target and it stops searching the overland route.

Infantry move faster over road surfaces so he follows it down before cutting across the grass. The short red line is part of his route around the cavalry unit which is blocking the path's tiles.

Meanwhile, the ship in the centre is following its own path (the other white line) through the water and across the shallows.

Hats off to our programmer extraordinaire, Philip!

[willliamV]

Looks brilliant...me want now!!

[SMST]

LOVE to see floating ships in the new system.

A little video would have been nice, though.=)

[Jeru]

I agree, it is high time for a video, we are more than willing to accept help with that.

[Exüberance]

Is that how shallows are going to look when the game is completed or are you going to add more visual clues like how they had lilypads in Age of Empires II?

Also, how will roads affect an army moving along it? Will slower units automatically move onto the road for a speed increase or will the army maintain formation?

Anyways, the water reflections look amazing. I normally don't care much about graphics in games, but wow. This looks really really good. Sounds like it's going to be rediculously fun too. I'm sure this game is going to become really really really really popular once it comes out. Glad that it will run on Linux too so I won't need WINE.

[omicron1]

Nice.

Couple questions:

1. How do transport ships figure into the pathfinding system?

2. How does the game handle long-range/en masse pathfinding checks (say you order fifty units from one end of a map to the other)?

3. If there's no path to find from one disconnected landmass/water mass to another, does your engine recognize this? It should be a relatively easy fix - a propagated key value for each group of pathfinding tiles, such that each water/land mass will in the end have its own key index, and such that a pathing request from one key index to a different key index will be a trivial case.

4. Have you thought of doing octree optimization on the pathfinding data? A simple largest-square finding algorithm could work; it would result in vast speed improvements at the cost of flexibility and path elegance.

[Ykkrosh]

Transport ships don't figure into it. (Should they? Seems more like a job for player micromanagement or for higher-level AI, not for the pathfinder.)

Group movement isn't handled specially yet (it'll just do fifty separate pathfindings). There ought to be a group/formation system so it computes a single long-range path and then each unit uses the short-range obstacle-avoiding pathfinder to chase its position in the group, or something like that.

There's no optimisation for unreachable destinations yet. That probably would be good, although if you select an unreachable target then the unit should move to the closest reachable point so I think it'll still need to do some kind of non-trivial search to find the goal tile. Also I expect it's a bit trickier when the goal is a circle/square (e.g. when an archer moves into attack range) rather than a point, because you can't simply check reachability of a single tile and there's too many different ranges to let you precompute it all. The complexity may still be worthwhile for performance, though.

There's loads of algorithmic optimisations that are possible - currently it's just a dumb brute force tiled-based A*, which is adequate for now since computers are good at brute force (it only takes milliseconds) but it really ought to be replaced with something cleverer. (Plus there's a dumb brute force visibility-graph A* for short-range obstacle avoidance, which is probably harder to optimise (everything keeps moving so you can't precompute much) but still has plenty of scope for improvements). My focus was on getting the gameplay functionality and the interfaces with the rest of the system working, so we can get on with testing the game, and hopefully someone with more time and/or pathfinding experience can improve the implementation in the future

[brettalton]

That's really interesting, I was just reading up on pathfinding at the Wolfire blog; http://blog.wolfire.com/2010/05/Pathfinding-with-Detour

Can't wait to see 0 A.D. in action

[omicron1]

I'd think you wouldn't want to use pathfinding for range checking. Much faster to keep an area-delineated tree list of units (so you don't have to check all of them to see which ones are in range) and check X/Y distances between them, no?

[omicron1]

EDIT: I misunderstood.

[juan56]

i hace a question?

what Heuristics metod used?, manhattan or diagonal short? your A* contain binary cells?

[Ykkrosh]

You can check the code for the full details . It doesn't do anything very fancy - it's a simple A* over the tiles (with no diagonal adjacencies) using a Euclidean heuristic, with some adjustments in the cost function to prefer 30/45-degree lines. (Then there's a separate A* over the visibility graph of nearby obstacles, so that units aren't restricted to tiles). Not sure what you mean by "binary cells".

[juan56]

Very interesting, excellent work you do. "Binary cells" sorry for my English I'm from Panama City in Latin America. It is a way to sort your lists your open and closed A *. Instead this is from largest to smallest, which are sorted by the closest to your target. Or find easier to explain the node with the lowest score F. Because a large map can be take more time to find the score F. time consuming. But with "Binary cells, can shorten the search. In the "Binary cells" also say "Binary Heaps":)

I am interested to learn all about the game's programming is amazing the work they have done.

[Ykkrosh]

Ah - binary heap is the standard English term . Actually it doesn't seem much faster in practice, compared to simply searching an unsorted array. The open list is typically quite small, so searches are not very expensive, and the array is much quicker for inserting and extracting and updating items than the heap. And the STL heap implementation in debug mode in Visual C++ is really really slow, so currently we just use the array instead. A better heap implementation or a different data structure (there was an article from (I think) Empire Earth suggesting an unsorted list plus a short fixed-length cache of smallest entries) would probably be a useful improvement.

[SMST]

I just found this video:

Good to see your system in action. Also, the new font looks a bit nicer than the old one.

[Mythos_Ruler]

nice, I also see some other new-ish videos posted there as well.