Polygons and microterrain

[Mark_Everson]

Hi KrikkitOne:

A move of one square in Clash does involve a different distance depending on whether it is diagonal or vertical/horizontal in squares. Diagonal moves cost 1.41x as much.

[KrikkitOne]

Oh, well in that case Squares are better [assuming that that diagonal=1.4 x applies to all distance based calculations]

Essentially they are a coordinate system then (just with very low resolution)

OK, I'm fully behind squares as the opponent of polygons

[Gary Thomas]

Travelling 4 spaces north and 3 east gives, with a little Pythagoras, a distance of 5, with a clearly defined shortest path. Using a square grid, the shortest distance is 5.2 (3 diagonal and 2 north moves), and the paths: (N-N-NE-NE-NE), (N-NE-N-NE-NE), (N-NE-NE-N-NE), (N-NE-NE-NE-N), (NE-N-N-NE-NE), (NE-N-NE-N-NE), (NE-N-NE-NE-N), (NE-NE-N-N-NE), (NE-NE-N-NE-N), (NE-NE-NE-N-N) are all minimal and of equal length. To try and advocate such a movement system as "simpler" must be extraordinarily difficult, and the effect on unit behaviour is nothing short of bizarre.

[KrikkitOne]

firstly its (3 NE and 1 N) second thats assuming that all the intervening squares are equally easy to pass through. *after all, the shortest path maybe 9 S,5 SW, 3NE, ............if you're going from Casablanca to Madrid by railroad for example.

[Gary Thomas]

Yeah, I miscounted the steps. So it has only 4 different shortest routes of 5.2 each. I don't think the Romans used railways much. Why not say "all distances are zero using teleportation, so don't bother with a map"? I was assuming "other things being equal", like all flat land.

Curiously enough, using a grid makes the pathfinding algorithm more complicated because it has to decide between all these different shortest routes.

Seeing my troops zig-zagging when I want them to go in a straight line has always irritated me.

[Mark_Everson]

Gary, since you're thumpin' on this so hard, do you know what the complexity is for discrete vs continuous coordinate pathfinding? I think continuous may be more expensive. I think the map AI ideas I've come up with would work with continuous coordinates, so I'm not terribly frightened so long as this stays in the Clash 2.0 sphere .

[Gary Thomas]

I haven't researched it fully yet. The pathfinding for continuous space is a two step process, but not wildly complicated.

One way is to overlay with a temporary square grid, calculate it as at present (but with the terrain boundaries correctly set in the square), then dispense with the grid, and tighten up the path (so it isn't forced through the centre of the grid squares). This works a bit like an elastic band. That is approximately how it works.

No big deal.

I have no time scale in mind for tryng this out. Some summer day, when the sun sign is Aquarius, and the beer is cold.

One of the goodies I didn't mention before is that you can scan a map from an atlas and use it pretty much directly.

Cheers

[Simon Loverix]

Gary, may I remember you of the possibility of describing the roughness of the terrain with a number between 0 and 1? That way there would rarely be equivalent shortest routes than with only 4 terrains. And you can take vegetation into account as well. With this kind of variability I assume armies would seldom go moonwalkin'.

Ah, a Summer vision.

[KrikkitOne]

In terms of movement, that is the primary point making sure the pathfinding AI can handle the system.

Since I really know nothing about AI, whether to make it continuous/discrete I'd leave up to those who do know which is more easy to give a 'sensible' pathfinding algorithm to.

However, a coordinate system for unit position is eessentially a square system, it just uses a lot smaller squares than are used for terain features.

[Gary Thomas]

However, a coordinate system for unit position is eessentially a square system, it just uses a lot smaller squares than are used for terain features.

It isn't quite, if lattitude and longintude are used, it is modified by the spherical shape of the earth. At the equator, and using float variables, the grid spacing is less than 50m. If double variables are used it is less than 50 nanometres.

I don't think it will be a problem.

Gary, may I remember you of the possibility of describing the roughness of the terrain with a number between 0 and 1? That way there would rarely be equivalent shortest routes than with only 4 terrains. And you can take vegetation into account as well. With this kind of variability I assume armies would seldom go moonwalkin'.

It isn't a good idea to rely on accidental features to cure an underlying fault in the model. What about aircraft and ships?

[Simon Loverix]

You're right, I forgot other-than-land movement.

The pathfinding problem is to find the places where a unit is when going from position one to position two. Is it possible to choose a possible route when a move order is given and then set several waypoints to keep that unit 'en route'? Recalculating the path would then only be necessary when something unexpected is encountered, or when new orders come.

With a coordinate system, when can units meet each other? How close do they need to be?

(I hope you didn't intentionally omit you cheers )

[Gary Thomas]

The pathfinding problem is to find the places where a unit is when going from position one to position two. Is it possible to choose a possible route when a move order is given and then set several waypoints to keep that unit 'en route'? Recalculating the path would then only be necessary when something unexpected is encountered, or when new orders come.

Finding out if something unexpected has happened takes about as much calculation as recalculating the path. It also depends on what the destination is (square or moving unit).

With a coordinate system, when can units meet each other? How close do they need to be?

Just think in terms of real life. Scouts might be aware of another force up to about 50km distant. A meeting engagement on a road, without scouts, probably about 2 km. For actual ancient style combat, 100 m or so.

Cheers

[Simon Loverix]

'Something unexpected' isn't that broad. Army approaching, new information available.. Couldn't such things alert the army/trader/whatever on a path?

In RL armies or travellers whatsoever usually travelled from town to town and only heard news when coming to a mayor settlement again. Is it possible to determine waypoints using this criterium? With low transport tech and few cities this would be appropriate, but using radio it would be irrelevant.

[Gary Thomas]

We could have wayside inns! And tinkers.

Anyway there would be no problem doing this.

Cheers

[Gary Thomas]

I haven't forgotten my favoutite hobby horse!

Cheers