Play Now Login Create Account
illyriad
  New Posts New Posts RSS Feed - Pathfinding - how hard is it?
  FAQ FAQ  Forum Search   Register Register  Login Login

Topic ClosedPathfinding - how hard is it?

 Post Reply Post Reply Page  123 5>
Author
 Rating: Topic Rating: 1 Votes, Average 5.00  Topic Search Topic Search  Topic Options Topic Options
Createure View Drop Down
Postmaster General
Postmaster General
Avatar

Joined: 07 Apr 2010
Location: uk
Status: Offline
Points: 1191
Direct Link To This Post Topic: Pathfinding - how hard is it?
    Posted: 19 Jan 2012 at 13:26
Just noticed an article about path-finding from another game which I imagine has holds some very similar issues to what the Illy dev team might be facing.

https://secure.8realms.com/m=news/g=8realms/show-me-the-way-to-go-home

Interestingly (or perhaps, obviously) it seems their exhaustive 'best route' path-finding algorithm worked well over short distances but they really had to cheat as the distances got bigger by effectively turning their worldmap into a grid of identical small maps, then when you want to cross the world map you use the 'best path' algorithm to find your way to the nearest 'node' on an adjacent grid tile and then your army just follows a preallocated 'best path' for crossing all the grid tiles between yourself and your target.

Clearly this approach would not work so easily in Illy - since every part of our world map is unique. I imagine though that you could save alot of processing time though by adopting a similar set of 'preallocated standard routes' (kind of like 'motorways/highways) forming a network that criss-crosses the entire Illy world map. Sure these would take an awefully long time to calculate (and would need to be recalculted if players started doing things like building bridges or ferry crossings or roads) but at least it would mean that large chunks of routes would not need to be recalculated every time a player sends a single scout to the other side of the world. Then, similar to the solution above - it would just be a question of calculating the fastest route to the nearest "motorway".

I imagine the dev team has already had these thoughts and much more besides - think it'd be interesting to see what the community thinks though. ^^

(P.S. regarding that link above - there's some interesting and fairly 'innovative' stuff in that game above - but as an Illy player I'd suggest you could probably do without wasting your time on it... I've played it about a month and i'm bored - there is no community, no chat, no lore+history, no PvP and the game mechanics are all pretty repetetive... it's like: build/research a load of stuff > advance to the next age > build/research all the same stuff again > advance > build/research all the same stuff again > advance... etc. - you do that about 8 times then the game ends.)


Edited by Createure - 19 Jan 2012 at 13:31
Back to Top
Quackers View Drop Down
Forum Warrior
Forum Warrior
Avatar

Joined: 19 Nov 2011
Location: Jeff City
Status: Offline
Points: 435
Direct Link To This Post Posted: 19 Jan 2012 at 15:38
This just made my head explode: http://www.pearltrees.com/#/N-play=1&N-u=1_100159&N-p=20725697&N-s=1_1189624&N-f=1_1189624&N-fa=1087564

I'm not good with computer stuff, but wouldn't this create a load on the servers? I mean we do have 55,646 moving caravans and 958,963 moving troops at the time of this post/edit. But it seems like a simple concept that could be easily adjusted to fit different variables so they might be using this. 

Edited by Quackers - 19 Jan 2012 at 15:42
Back to Top
Angrim View Drop Down
Postmaster General
Postmaster General
Avatar

Joined: 02 Nov 2011
Location: Laoshin
Status: Offline
Points: 1212
Direct Link To This Post Posted: 19 Jan 2012 at 18:11
This may explain the intention to route most caravan traffic to trade hubs via trade 2.0, keeping the bulk of the traffic in a local pattern.

You might also save some cycles by defining border crossings between areas.  Since most borders are defined by rivers, they could take the form of known fords/ports/ferries, with the intention of separating the work of pathfinding into multiple smaller trips.
Back to Top
Quackers View Drop Down
Forum Warrior
Forum Warrior
Avatar

Joined: 19 Nov 2011
Location: Jeff City
Status: Offline
Points: 435
Direct Link To This Post Posted: 19 Jan 2012 at 18:29
Originally posted by Angrim Angrim wrote:

This may explain the intention to route most caravan traffic to trade hubs via trade 2.0, keeping the bulk of the traffic in a local pattern.

You might also save some cycles by defining border crossings between areas.  Since most borders are defined by rivers, they could take the form of known fords/ports/ferries, with the intention of separating the work of pathfinding into multiple smaller trips.


That is very smart thinking and that does make sense. So will a GM reply if they are doing it this way, or if they are working on their own special way?

Would this way allow them to expand on the pathfinding and allow them to do all objectives they wish to do?
Back to Top
Albatross View Drop Down
Postmaster General
Postmaster General


Joined: 11 May 2011
Status: Offline
Points: 1118
Direct Link To This Post Posted: 19 Jan 2012 at 18:44
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.

This is a significant programming challenge, and it's going to take time (especially the last 5%!)

People write academic papers on this subject, and it [path-finding AI] is often the part that lets down an otherwise good game.
Back to Top
KillerPoodle View Drop Down
Postmaster General
Postmaster General
Avatar

Joined: 23 Feb 2010
Status: Offline
Points: 1853
Direct Link To This Post Posted: 19 Jan 2012 at 18:47
My expectation is that the devs will provide the mechanism for border crossings (e.g. Bridge building) and expect us to build the bridges.  Could make for fun times trading until folks get infrastructure built up.
"This is a bad idea and we shouldn't do it." - endorsement by HM

"a little name-calling is a positive thing." - Rill
Back to Top
Createure View Drop Down
Postmaster General
Postmaster General
Avatar

Joined: 07 Apr 2010
Location: uk
Status: Offline
Points: 1191
Direct Link To This Post Posted: 19 Jan 2012 at 19:14
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
Back to Top
Rill View Drop Down
Postmaster General
Postmaster General
Avatar
Player Council - Geographer

Joined: 17 Jun 2011
Location: California
Status: Offline
Points: 7078
Direct Link To This Post Posted: 19 Jan 2012 at 19:44
What I find exciting is the prospect that pathfinding could occur "in the cloud."  The devs have said that google has offered intriguing possibilities in terms of basically doing pathfinding similarly to the way GPS works in the real world.  This would perhaps imply that there would be a number of pre-calculated "best routes" that would then be altered by player construction activity.
Back to Top
Createure View Drop Down
Postmaster General
Postmaster General
Avatar

Joined: 07 Apr 2010
Location: uk
Status: Offline
Points: 1191
Direct Link To This Post Posted: 19 Jan 2012 at 20:04
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
Back to Top
GM Stormcrow View Drop Down
Moderator Group
Moderator Group
Avatar
GM

Joined: 23 Feb 2010
Location: Illyria
Status: Offline
Points: 3926
Direct Link To This Post Posted: 19 Jan 2012 at 21:16
Interesting thread, as ever from our playerbase.

Pathfinding is, indeed, a big issue.

I asked TC if he wanted to comment in this thread, and he said (and I quote):

"GM ThunderCat has a black box he make magic in - it uses high speed fundamental particles moving at fraction of the speed of light to... well maybe you should write the response..."

So here goes!

Pathfinding algorithms themselves, whether they be A* or variants like Dijkstra, Manhattan or whatever - well, programmatically... these are actually quite simple.  More complex (but implementable) are concepts such as nodal or neural-network pathing via functions such as MapReduce.  There are similarities and parallels between distributed computing algorithms and gameplay pathfinding, strange as it may seem.

The key, as mentioned in this thread, is building it to work with the number of concurrent unit groups moving, and to what extent we need to consider changing conditions (such as interception / collisions / proximity events and triggers).

The answer is, ofc, a hybrid solution of getting the moving unit to the first pre-defined node and then moving it along that pre-defined path until it exits to its final destination, as well as balancing gameplay and what functions we permit players to carry out.

The suggestion that we may have planned rivers, terrain and other natural boundaries around subdividing the areas that nodes might interconnect in... well, that's wise people saying wise things Big smile

However, pre-mapped "main route" nodes are themselves highly variable and applicable situationally.  

There are multiple suitable nodes according to different (and shifting) parameters, supplied by the player-map-architecture itself.

To explain with an example:

  • Player A wants to send units to Location Z
  • There are multiple possible routes from Player A to Location Z
  • Many of these involve nodal pathways that may not be suitable to the player
  • For example: 
    • Player A may want the quickest path (time-wise), so doesn't care about (eg) tolls for crossing the player-owned bridges
    • Player A may want the cheapest path (eg time is a less important parameter), so wants to avoid toll bridges along the way
    • Player A may want the safest path (eg getting there is the most important parameter), so wants to avoid nodes where hostile Alliance B is in control, or where more than X casualties have occurred in the vicinity, in the last Y hours.
    • Player A may want to set his or her own manual waypoints with changing pathfinding preferences along the way - eg pathfind to point A and then to point B (via this major nodal road connection between A and B) and then to point C (but avoiding roads and danger areas whilst you travel to point C)
There are further nodal generations beyond the obvious and pre-defined (ie bridge crossings).

For example, the system can learn from what players provide as manual waypoints.

eg. A bunch of players who continually set a manual waypoint in a map-cluster to avoid paying the toll at bridge X... well, the system can learn that this is a good waypoint for everyone to use who has a "cheapest route first" preference (at the potential sacrifice of time, bandits, interception etc).

In terms of CPU cycles and server-load.  Yes, this is precisely the kind of thing the cloud is very good at - scaling to solve large problems without compromising the core, and this is where we are seeking our solutions.

Obviously User Interface has to be as clear and simple as possible, and this is going to be a challenge to get right.  For many players, the simple "go from X to Y fastest/safest/cheapest" will be used in the main, but for many of the more involved strategists they're going to want to build their own routes manually (and perhaps save them for future recall, or share them with their alliance).

Unexpectedly, perhaps - but as a side-effect of the fact that we're not (by background) game developers ourselves - we have prior commercial world experience of the same problems we face with pathfinding in Illy.

Blowing own corporate trumpet slightly, but to give credit where it's due (and he hasn't asked me to share this, I just think I should in this circumstance): 

GM Thundercat, in a previous incarnation as Head of Innovation for a major international company, won the 2009 Best Practice in Data Management Award by working on precisely these kind of pathfinding problems, simply applied in the real world through a project of his called "Walklist".

I've looked back through our old chatlogs, and a good while back we discussed pathfinding (and his experiences with it).  TC said at the time that "When they went to test it (by walking the routes themselves) they kept as asking for more routes as they "weren't sure". I took that as I'd done something horribly wrong. Turned out they wanted to make sure it was repeatable as it was like some kind of voodoo magic.  I wasn't sure how to take it - I think it was a compliment"

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.  As it were. 

In short, pathfinding is a really big issue that grows with the number of parameters and units in motion but we think we have it in hand.

Best,

SC
Back to Top
 Post Reply Post Reply Page  123 5>
  Share Topic   

Forum Jump Forum Permissions View Drop Down

Forum Software by Web Wiz Forums® version 12.03
Copyright ©2001-2019 Web Wiz Ltd.