Pathfinding - how hard is it?

I'm secretly wondering whether terrain modifications (or superimposed vectors) like trade routes will be made significantly easier to traverse than naked landscape, just because it makes the trunk routes the most efficient default option, and the right choice is most cases. I'm also wondering whether the naked landscape will be made more difficult to traverse, just to help this along.

GM Stormcrow wrote: Our shared commercial background is broadly with extracting the dataset marrow from the value-bones of gargantuan problem-dinosaurs, and then extracting the algorithmic DNA to build even more deadly-efficient gaming veloci-raptors.

This sentence has to go down in the annals of Illy history as SC at his SCyest... ;)

See what you mean - although strangely enough although Illy is a game and the real world is real - the pathfinding conundrums in Illy are potentially vastly more complex than any kind of real world gps problem.

There is only a limited different number of non-redundant ways of getting from A to B on roads in the real world, since there are only a certain number of roads you can travel along - in Illy you would be able to imagine an almost infinite different number of ways of getting around. Sure a human would instantly be able to cancel out a huge proportion of these options but if you're trying to get a computer to calculate a long optimal route on a huge topographically varying grid like Illy it could be at it for years unless you impose a whole bunch of restrictions to simplify the problem.


Edited by Createure - 19 Jan 2012 at 20:05

Yeh I guess the idea of 'bridges' or other types of crossing point between seperate areas effectively the same idea as the 8Realm "node" idea - each 'bridge' effectively becomes a 'node' seperating two seperate regions - then, the same as the 8realm siplification - each journey between seperate regions becomes a question of travelling to the nearest 'node' (using the A* method or any of its variants) and then following a pre-calculated standard route between nodes to the nearest node to the destination, and then calculating the shortest route from this node to the terminus - and hence massively decreasing the amount of computation required.

Only problem is... you are not gauranteed a 100% optimal path, the path to the nearest node can be optimal and so can the paths between nodes - but there may well be a better route that does not involve travelling to the nearest node.

And the other problem is that standard routes would have to be added/removed/recaluted regularly as player interactions affect the availability of nodes (if/when that is implemented).

I reckon that the dev team were actually considering some of the difficulties of path-finding when they decided where to put the river+lakes. Specifically for the purpose above - to break the map down into smaller sections to make route calculations slightly more bite-size.


Edited by Createure - 19 Jan 2012 at 19:28

Pathfinding is very difficult to do well, and solutions have to be re-engineered for every different representation of the world. e.g. vector/polygon worlds and cellular maps can be optimized differently. Off the top of my head, the Illy situation doesn't look trivial either, especially because pre-processing optimisations wouldn't be relevant to all possible variables, which discourages re-use of computations; it's not just a matter of using a single 'weighting' value to each cell, and plotting the best path.