Pathfinding - how hard is it?

(2n!)/((n!)(n!))

The phrase "capacitated vehicle routing problem with time windows" - brings back such lovely memories...

Yes Nesse pathfinding is very simple in the case you describe where you are finding best path from 1 square to an adjacent square.

What you are not considering is that in order to find the best route between two points 500 squares apart you do not just consider each movement 1 square at a time, so it is not just an 'additive' problem in terms of processing time required.

If you take a very simple example with all squares having equal weight - [mountains are same speed as water and plains and forests] - and say that in order to get from point at square [0,0] to square [100,100] you will at minimum need to make 200 steps assuming you can only move directly north or east. If you think about it, there is 100! [aka 100*99*98*97*96*...*3*2*1] different ways of getting from [0,0] to [100,100] in this very simple manner... if you try and work out what number that is you will get MATH ERROR - i.e a very very very big number.

Now consider what path-finding is actually about - it is finding the best (definition of 'best' may change) route between two or more states (locations or whatever). But basically what i'm saying is that in order to find a route you best matches certain criteria, you need to consider ALL the routes. This means that you now have to ask your processor to consider 100! routes in order to find the particular one (or ones) that best match your criteria.

As you can see my simple example is rather simple, real movement in Illy path-finding would certainly be considerably more complex than just moving north/south or east/west on uniform topography - for example it could involve moving away from your destination to begin with in order to get to a road or to circumvent a mountain range or ocean - conditions like this basically mean you have to loosen the restrictions that you place on the range of paths that your system needs to consider in order to pick one... so your 100! number is going to rise dramatically.

What we've all been discussing above is various ways to reduce this 100! number by putting conditions on how many different paths you need to consider. (or the frequency with which you need to consider them) One solution here - as I pointed out in the opening post - is to break the journey down into smaller blocks, like they suggested in that link. For example if you are travelling to 100,100 from 0,0 but you say that you have to pass through 25,25 on the way then you will find the number of possible paths reduces from 100! to 50! + 50! which you will find does fit into the memory of a standard calculator - around 6.1*10^64 different paths. The clever thing here is how you chose to split your journey up.

Obviously breaking the world map up in to equal dimensioned blocks is pretty clumsy but does the job, this is what the 8Realms guys basically did in that article I linked. Various suggestions for breaking journeys in Illy up have already been given by players and devs above and I guess the answer will largely lie in a huge amorphous mutant mess of all of them - but largely starting with the existing topography in Illy - as SC has already pretty much confirmed, when the devs designed the world map they designed it so that various locations would be nicely split up by natural boundries so that complexity of paths for consideration would be reduced.

edit:

100 ! = 9.33262154 × 10¹⁵⁷

Thanks Google... it has more memories than my pocket calculator.

Edited by Createure - 25 Jan 2012 at 16:32

As we are mere ants in this vast Illyria multiverse perhaps ant colony optimization algorithms may be useful.

GM Stormcrow wrote: What amuses me the most is that of all the people who have ever worked on the intractible "travelling salesman" problem, TC is probably one of the few who has worked sucessfully on, quite literally, that precise problem

TC is dot-to-dot pro?


I'm intrigued to learn more about this "Cloud" thing getting mentioned - as far as i'm aware it could be a real cloud that floats above elgea to keep it cool and shady so it can calculate x% more alternative paths per second.

Edited by Createure - 20 Jan 2012 at 01:09