Pathfinding - how hard is it?
Printed From: Illyriad
Category: Miscellaneous
Forum Name: The Caravanserai
Forum Description: A place to just chat about whatever takes your fancy, whether it's about Illyriad or not.
URL: http://forum.illyriad.co.uk/forum_posts.asp?TID=3088
Printed Date: 16 Apr 2022 at 21:56
Software Version: Web Wiz Forums 12.03 - http://www.webwizforums.com
Topic: Pathfinding - how hard is it?
Posted By: Createure
Subject: Pathfinding - how hard is it?
Date 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" rel="nofollow - 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.) |
Replies:
Posted By: Quackers
Date 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" rel="nofollow - 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. |
Posted By: Angrim
Date 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.
|
Posted By: Quackers
Date 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? |
Angrim wrote:Posted By: Albatross
Date 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. |
Posted By: KillerPoodle
Date 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 |
Posted By: Createure
Date 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. |
Posted By: Rill
Date 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. |
Posted By: Createure
Date 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. |
Posted By: GM Stormcrow
Date 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 http://en.wikipedia.org/wiki/MapReduce" rel="nofollow - 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 http://press.experian.com/United-Kingdom/Press-Release/experian-scoops-raft-of-awards-and-wins-top-accolade-at-2009-data-strategy-awards.aspx?&p=1" rel="nofollow - 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
|
Posted By: Kumomoto
Date Posted: 19 Jan 2012 at 21:56
This sentence has to go down in the annals of Illy history as SC at his SCyest... ;) |
Posted By: GM ThunderCat
Date Posted: 19 Jan 2012 at 23:16
|
And of course add into the mix path intersections for interception, ambushes and whatnot...
Of course over varying speed terrain - shortest path to intercept, or safest route to interception? Will the interceptors themselves be ambushed? Or the ambushers intercepted by further group moving over the quickest route...
|
Posted By: Albatross
Date Posted: 19 Jan 2012 at 23:45
|
Pointless speculation, but nonetheless fun (for me at least) ... |
Posted By: GM Stormcrow
Date Posted: 20 Jan 2012 at 00:26
|
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
|
Posted By: Createure
Date Posted: 20 Jan 2012 at 01:08
He takes the bait - hook, line and sinker. ^^
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. |
Posted By: GM Luna
Date Posted: 20 Jan 2012 at 01:16
Also my new favorite sentence ever. Luna ------------- GM Luna | Illyriad Community Manager | community@illyriad.co.uk 
|
Posted By: Bonaparta
Date Posted: 20 Jan 2012 at 02:05
| As we are mere ants in this vast Illyria multiverse perhaps ant colony optimization algorithms may be useful. |
Posted By: Nesse
Date Posted: 25 Jan 2012 at 15:21
Being a scientist by trade, the post by SC about pathfinding makes me a bit worried about the complexity that seems to be considered necessary for intruducing terrain effects into the game, e.g.:
How about starting with straight line movement along the eight directions S, N, E, W, NE, SW, NW and SE? Add movement costs as speed reductions, e.g. 50% for large mountains and forests, less reduction for the small variants and hills, and an equivalent of adding two squares extra cost to start moving across water. Then pick the closest combination of two of the eight directions and make straight line movement in first one, then the other direction (pick the one of the two choices that is fastest). Since you would be moving through squares straight or diagonally, calculating the speed and travel times would be quite easy. Just as a teaser for more advanced things to come, and to get payers used to moving at terrain costs. As a research option, adding waypoints to the travel path would be neat, one additional point at the time at increasingly expensive and time consuming research options. Then you could later introduce "Thundercats second pathfinding algorithm" as a research option. Possibly later made obsolete by the introduction of "Thundercats third pathfinding algorithm, necessitating renewed research efforts. |
Posted By: Createure
Date Posted: 25 Jan 2012 at 16:11
|
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 × 10157Thanks Google... it has more memories than my pocket calculator. |
Posted By: GM Stormcrow
Date Posted: 25 Jan 2012 at 17:43
|
Nesse - Yes, as Createure has essentially pointed out, "algorithmically easy" does not equal "CPU cycle feasible". We're reasonably confident we have this in hand, though, as well as pre-experience of much, much more complex real-world implementations (considering square-to-square movement cost in 8 directions is much, much simpler than planning multi-dimensional pathfinding, such as walking door-to-door across a tower-block housing estate). SC
|
Posted By: GM ThunderCat
Date Posted: 25 Jan 2012 at 18:34
| The phrase "capacitated vehicle routing problem with time windows" - brings back such lovely memories... |
Posted By: Createure
Date Posted: 25 Jan 2012 at 18:39
|
Also I just realised I was correct in the "very large" part of the number example but incorrect in saying it was a factorial thing - it does seem to be an exponential of some for looking at the straight line on a log-linear plot of the first few terms. If anyone wants to prove they are more switched on/than me today give me a mathematical description for the sequence that starts: 1, 2, 6, 20, 70, 252, 926 And I will give you 1,000 cows if you can do it - math teim.  p.s. the answer for n=100 is: 267823007376670171763904352500539254130289039388032841724230 |
Posted By: Ander
Date Posted: 25 Jan 2012 at 19:10
|
(2n!)/((n!)(n!)) 500 cows to google and 500 to wikipedia
 |
Posted By: Createure
Date Posted: 25 Jan 2012 at 19:19
Nice try, not quite though. Assuming you meant (2n)! / 2*(n!) you get the sequence: 1 2 6 60 840 Or probably just a case of "wrongipedia" - answer is (2n)!/(n!)^2 |
Posted By: Ander
Date Posted: 25 Jan 2012 at 19:29
Why assumed 2*?  I meant (n!)*(n!). Since there is no option to write 'n! squared', I just chose to put it (n!)(n!) I didnt mean to hijack the exciting thread. Too brainy for me. Please carry on you sparky folks! http://en.wikipedia.org/wiki/Central_binomial_coefficient" rel="nofollow - http://en.wikipedia.org/wiki/Central_binomial_coefficient
|
Posted By: lisao
Date Posted: 25 Jan 2012 at 19:29
|
It is twelve years since I did any pathfinding, it is a very fascinating problem. Easy on a casual look, but very complex if you have processor and/or memoryconstraints. The solution should be (2n!) / (2n!)^2. The central part of pascals triangle. |
Posted By: Createure
Date Posted: 25 Jan 2012 at 19:34
Just bracket confusion going on. TC seems very quietly confident about all this schabang. As I've just proved even relatively simple examples of pathfinding have the ability to confound people like me relatively rapidly when scaled up. Mucho respect. |
Posted By: Ander
Date Posted: 25 Jan 2012 at 19:40
No, lisao is wrong!
It should be (2n!) / (n!)^2 |
Posted By: Nesse
Date Posted: 25 Jan 2012 at 20:25
|
No, you misunderstand me, Creature and Stormcrow! What I am saying is NEVER MIND finding the closest, fastest or most direct route. That would not be the way it would be done in medieval times anyway. Instead, to go between ANY two points, not necessarily adjacent, choose one direction, until another direction is shorter. Or to make it even simpler, use only four directions. Then, going from (167,148) to (16,3) you would choose both A) first the straight line from (167,148) to (167,3), then straight line (167,3) to (16,3) or B) first the straight line from (167,148) to (16,148), then straight line (16,148) to (16,3) Then calculate which of those two is fastest (that's evaluating the terrain effects in 2*(151+145) squares, give or take four, but that should not take long, since the traveled route in all swuares except the end squares is exactly one square). Oh, and then add the diagonals, making it marginally more difficult to find which two lines are "closest", and using traveled distance sqrt(2) per square for the diagonal. But what would be fun would be using your own waypoints - maybe it would take research to establish the waypoint for caravans from that town? |
Posted By: Nesse
Date Posted: 25 Jan 2012 at 21:04
|
And yes, I get the pascal triangle bit too, but apart from not being the likely procedure for a caravan commander it is also too restrictive - you would like to travel in straight lines across same kind of terrain, turning at a well defined angle going from one terrain to another, rather than going stepwise square-by-square. There are obviously algorithms for that too, which I am sure Thundercat is infinitely (or at least n!) more familiar with than I am. But what I'm trying to say is: don't overdo the "fastest" bit in fastest route! Also an extremely crude algorithm for finding a POSSIBLE route would be a good start and a welcome change from the flying caravans of today. We, or at least I, would not expect my caravan drivers to do any better than stumbling along, and eventually getting there unless hijacked on the way. I might consider setting an ambush in a strategic position that wealthy caravans might pass, but interception I wouldn't even contemplate unless I had much faster units to send out to follow the enemy's footprints. |
Posted By: Createure
Date Posted: 25 Jan 2012 at 22:17
Ahh but this is Illy - we aren't happy with the crude approach! We want cutting-edge approaches to the design from our devs and intricate gaming strategy and community interaction in our MMORTS so that ThunderCrow and StormCat can become buried under a heap of gold-plated game designers' awards and we can all become more deadly-efficient gaming veloci-raptors! Personally I'm happy to wait that bit longer until we have something closer to this utopian ideal. |
Posted By: Albatross
Date Posted: 26 Jan 2012 at 00:16
|
:o) And after all this speculation about how hard it is, it will still be released in its own good time, using knowledge brought to the project from previous experience, fitting into that niche long-saved for it. "and SC saw that it was good" - HonouredMule, August 2012.
|
Posted By: abstractdream
Date Posted: 26 Jan 2012 at 01:41
|
Certainly the implementation of pathfinding will be an elegant endeavor, if what Illyriad is now is any indication. This is a game that has never let me down and I'm sure it won't with this. I really enjoy this thread, the speculation from players with more brains than I and the trickling of information from the GMs. I'm sure I speak for everyone in Elgea when I say: ------------- |
Posted By: GM Stormcrow
Date Posted: 26 Jan 2012 at 03:16
Whilst also being a better solution (I'm not quite sure what lesser/quicker/simpler approximations without terrain cost of movement etc actually bring to the gameplay end of Illy...?), there's also the commercial reality that work performed on the more difficult 'intractable' end of the underlying problem qualify for R&D HMRC Tax Credits for Illy Corp SC
|
Posted By: Rill
Date Posted: 26 Jan 2012 at 03:31
And if we were a bit more forward-looking, this fabulous company could be based in the United States ...
|
Posted By: Ander
Date Posted: 26 Jan 2012 at 07:52
That is not really a crude approach. The game can have it's own method for the fastest and cheapest route for King Sigurd's convoys to travel, but the default paths available to the players could be variant paths based on a straight line from the starting point to the destination. The better routes are best left for the players to find out based on their experience and situation. If the system is to present all the best possible paths, what is in it for players?
|
Posted By: Ander
Date Posted: 26 Jan 2012 at 07:56
someone would patent snuggling and our chat could get banned!
 |
Posted By: Createure
Date Posted: 26 Jan 2012 at 10:48
This is what the player before suggested I think (roughly) - citing "this is more like what they would do in medieval times" as justification - in response to that guy: firstly I don't want Illy to be like anything else, I want it to be original and excellent on it's own merits, not an imitation. Secondly, in medieval times would the caravan have spent 2 weeks climbing directly over mount doom and across the chasm of death, then swimming across a shark infested pond, rather that simply walking around? No I don't think so. Straight lines is clearly NOT an intelligent or a fun way to have movement of our in-game units.
|
Posted By: Nesse
Date Posted: 26 Jan 2012 at 12:02
You still misunderstand my post, Stormcrow! What I say is to start by introducing, as you put it "terrain cost of movement", but WITHOUT the hazzle of optimal paths. Just make it straight-line movement, in lines defined by the players. My suggestion was to restrict it further to only allow 8 directions. Actually, the choice between any combination of directions would not be necessary if you require the player to set a waypoint - then you only need to check if the waypoint is on a gridline from the starting point. Example 1: I want to move from (0,0) to (60,34), having researched "axis movement" and one waypoint. Setting the waypoint anywhere but (0,34) or (60,0) would give me an error message, using any of those two points would give the calculated travel time and a "confirm" button. Example 2: I want to move from (0,0) to (60,34), having researched "axis and diagonal movement" and one waypoint. I would now have between 8 and 12 options depending on whether the diagonals work, but the computational effort would still be limited to checking if the move is allowed and adding the movement costs of the involved squares. Example 3: I want to move from (0,0) to (60,34), having researched "axis and diagonal movement" and two waypoints.
Choosing the first waypoint would be checked only by ascertaining if it is on an allowed line going out from the origin, while checking the second point would be as per example 2. Calculation of distance is still only summing terrain costs for traversed hexes. Example 4: I want to move from (0,0) to (60,34), having researched "Thundercats wonderful shortest path avoiding all dangers".
I just select the target square, looks at the travel time, checks accept and off the caravan goes, calculations proceeding in a less than 2n!/(n!)^2 complexity that I will not notice except as a smooth and safe movement of my caravan. Straight lines, rather than restricted grid directions might be simple enough to calculate costs for to not motivate the rather artificial limitation of using only grid directions. But I think player defined waypoints is actually quite as good as automatic shortest distances. (Obviously, that opinion is disputed.) |
Posted By: Createure
Date Posted: 26 Jan 2012 at 14:53
|
I don't think we misunderstood you Nesse, I just don't think it is a good idea. It is basically exactly the same as what we currently have with a few small differences. 1) There are waypoints. 2) Instead of moving in an 'as the bird flies' manner like we do currently people are restricted to only moving in the Cardinal+Ordinal directions. (I.e. you move across adjacent tiles). These are both aspects that will be in path-finding when it arrives - great. But you are saying that we then don't need path-finding? We need no automated system for calculating routes? Personally I do not want to spend a hour hand picking a route around all the hundreads of obstacles across thousands of squares every time I send units across the Illy world map. This is a thread for the discussion of the implementation of path-finding - not for the discussion of whether or not we should have it at all. The fact is the dev team have already said we are having path-finding: you must be one of a very small number of people who actually think this is somehow a bad idea. |
Posted By: Kumomoto
Date Posted: 26 Jan 2012 at 16:07
What are you talking about, Creat? You know full well that we at H? always climb directly over Mount Doom (the volcanic ash has a marvelous exfoliating quality) and that treatment is always best followed by a quick dip in the fishy pond. Those cute and cuddly Carcharadons have a marvelous ability to remove dead skin (like those spas in Japan where fish nibble your feet)... ;) |
Posted By: Nesse
Date Posted: 27 Jan 2012 at 09:32
|
Creature, look at my "Example 4". I do want pathfinding, I just don't want to wait for it to be perfect before I get it.
|
Posted By: Thexion
Date Posted: 27 Jan 2012 at 12:40
|
Just to mix this convo a bit.. I'm just thinking what are important aspects for the game play in pathfinding. And how these could be simplified to creas horror. Main reason of pathfinding is that there are impassable squares in the map. No point for boats if units can fly over water. So you need at least "find your path" through rivers and lakes pass crossings and such. - This is hard to simplify but if units could make rafts and move very slowly cross water if there is no alternative.. hardly a realistic or satisfying solution but if there is no bridges or ferries to some places.. also it would simplify the pathfinding. Second reason is that different passable square types that give different moving speed. -One option to simplify is that in areas of terrain speed is generalized instead of counting each square. Third reason of pathfinding is that the caravans and troops would be on the map also physically in some square and so could be intercepted. -How this could be simplified is that only units that are set to intercept in certain areas would. And only when unit is near some intercepting unit it exact location would be decided. Also one question is that what will happen if the path that is pre-calculated would be blocked.. Would troops return home, set a camp, try to find a alternative way on its own? One issue is fog of war if it is introduced what does caravan know.. would it know automatically that all the bridges to certain place are blocked? And if it is trying to use the safest way how it would decide what is safest? Anyhow I have full trust in TC:s magics and all the goodness that is going to be better than it should be and is coming soon(TM) I hope.
|