Pathfinding - how hard is it? |
Post Reply | Page 123 5> |
Author | |
Createure
Postmaster General Joined: 07 Apr 2010 Location: uk Status: Offline Points: 1191 |
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 |
|
Quackers
Forum Warrior Joined: 19 Nov 2011 Location: Jeff City Status: Offline Points: 435 |
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 |
|
Angrim
Postmaster General Joined: 02 Nov 2011 Location: Laoshin Status: Offline Points: 1212 |
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.
|
|
Quackers
Forum Warrior Joined: 19 Nov 2011 Location: Jeff City Status: Offline Points: 435 |
Posted: 19 Jan 2012 at 18:29 |
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? |
|
Albatross
Postmaster General Joined: 11 May 2011 Status: Offline Points: 1118 |
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. |
|
KillerPoodle
Postmaster General Joined: 23 Feb 2010 Status: Offline Points: 1853 |
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 |
|
Createure
Postmaster General Joined: 07 Apr 2010 Location: uk Status: Offline Points: 1191 |
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 |
|
Rill
Postmaster General Player Council - Geographer Joined: 17 Jun 2011 Location: California Status: Offline Points: 7078 |
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.
|
|
Createure
Postmaster General Joined: 07 Apr 2010 Location: uk Status: Offline Points: 1191 |
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 |
|
GM Stormcrow
Moderator Group GM Joined: 23 Feb 2010 Location: Illyria Status: Offline Points: 3926 |
Posted: 19 Jan 2012 at 21:16 |
Interesting thread, as ever from our playerbase. 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 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:
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
|
|
Post Reply | Page 123 5> |
Tweet
|
Forum Jump | Forum Permissions You cannot post new topics in this forum You cannot reply to topics in this forum You cannot delete your posts in this forum You cannot edit your posts in this forum You cannot create polls in this forum You cannot vote in polls in this forum |