Lord Ba'al
Supreme Deity
Posts: 6,260
Pledge level: Half a Partner
I like: Cats; single malt Scotch; Stargate; Amiga; fried potatoes; retro gaming; cheese; snickers; sticky tape.
I don't like: Dimples in the bottom of scotch bottles; Facebook games masquerading as godgames.
Steam: stonelesscutter
GOG: stonelesscutter
|
Post by Lord Ba'al on Jul 19, 2014 7:16:43 GMT
I just thought of the solution to all of Lumberjack's path finding problems. Program some wings on the motherfucker.
|
|
|
Post by Danjal on Jul 19, 2014 8:46:13 GMT
Even when you'd give them wings (or allowing them to phase through objects) - that wouldn't solve the problem. The big issue isn't a single lumberjack pathfinding his way around and calculating this through your 'offline period'.
To stick to the banished example (because Banished has the whole population simulation down). A 200 pop town ends up with a bunch of farmers, foresters, woodcutters, forages, fishers and other professions. Each of these have their own pathfinding.
Yet Banished has distinct limitations. Each 'worker' has a restricted field in which he plies his trade - exception being builders that can roam around quite far. You might have seen the deathmarches caused when a builder believes the best course of action for building a bridge is to go the long way around? Another limitation in Banished is the map, its not indefinite, the map is finite. A third limitation is that Banished is SP exclusively. Its all happening in real-time.
Now I won't claim that Banished has a perfect pathfinding system - improvements can always be made. But even the most efficient system you could make would fall victim to exponential growth. Already Godus is looking at population counts in the thousands *per player*. Granted, a large portion of these are breeders that can theoretically (for now) be kept inside if you don't take the follower friendship upgrade.
But lets assume for a second that all these breeders are affected by that meaning that 100% of your population roams around and has some degree of pathfinding active. Now we're looking at 4 players per hubworld I believe? So we're looking at 20~24k population roaming around on a single hub (as far as is currently explained). In the current version of Godus there is no pathfinding going on like that, this is why we're finding followers lost on the tops of mountains.
Now I'm assuming here that in the future, Godus' population requirements will increase as the ages go up. So we're looking at upwards of 20k pathfinding tasks per hub, multiplied by the number of hubs. No matter how good your system is... Thats gonna be painful to run.
Possible? Yes... Especially when using tricks to fudge the reality. But painful still. (Personally I still don't believe that Godus can ever run the online bit the way it originally described it, and I'm fairly certain that it'll be entirely instanced and only active for the ACTIVE players while the others just have some numbers running in the background at best.)
|
|
splitterwind
Master
Posts: 149
I don't like: Ignoring a unpleasant question or answering with something that is only loosely related or way to vague to actually answer something. Mods that Cherry-pick in discussions. Banning people for minor offenses.
|
Post by splitterwind on Jul 19, 2014 12:08:52 GMT
Now you write a function that discards all the areas of the map that can not possibly be reached and stores the remaining coordinates in an array of some sort. Such optimizations and others are already done. Banished additionally divides the world in bigger quadrants and remembers its neighbors for each quadrant. It only pathfinds between the bigger quadrants and only performs detailed pathfinding in the current quadrant. That drastically limits the maximal number of fields that need to be examined. www.banishedforum.com/viewtopic.php?f=2&t=1155banished-wiki.com/wiki/PathfindingThe most common algorithm is A star or an variation of it (http://en.wikipedia.org/wiki/A*_search_algorithm). A star already uses heuristics to try to disregard any field that likely wouldn't lead to the target. Banished use such an algorithm like nearly every other game does. Now I won't claim that Banished has a perfect pathfinding system - improvements can always be made. It's not perfect but its already one of the better implementations. Anno 1404 did something similar. They pre-calculated nodes for each map. But only for the water and it makes sense because most of it is open space and water doesn't change while playing. static2.cdn.ubi.com/emea/gamesites/anno/pc/content/devdiaries/devdiary1404_4_4.jpganno.de.ubi.com/devdiary.php?diary=devdiary_1404_4 (german devdiary) That wouldn't realistically work on a jupiter sized map that is constantly changing. Also if I understood you right and you think about saving each possible route for every coordinate you would probably end up with an array that is bigger then the number of atoms in the observable universe... And every time someone performs terraforming or build something big parts of it need to be updated. Let's say you start with a node, now place 4 nodes around it (5 nodes) Now add 4 nodes to the other 4 nodes and you already have 16 additional nodes. Do that again and you can add another 64 nodes. Do that a few times and you end up with a unbelievably huge number that will only get bigger (We're talking about a jupiter sized world). And then try to calculate each possible route from each node to every single other node instead of just its neighbors... I think even with a small number of nodes you would reach the realistic limit. en.wikipedia.org/wiki/Wheat_and_chessboard_problemBut even the most efficient system you could make would fall victim to exponential growth. Exactly.
|
|
splitterwind
Master
Posts: 149
I don't like: Ignoring a unpleasant question or answering with something that is only loosely related or way to vague to actually answer something. Mods that Cherry-pick in discussions. Banning people for minor offenses.
|
Post by splitterwind on Jul 19, 2014 12:15:21 GMT
Slightly related. There is the attempt to use search algorithms to display graphics with unlimited details (graphics so good and detailed that you can't improve them any further). The problem is saving the world and animating it.
|
|
Lord Ba'al
Supreme Deity
Posts: 6,260
Pledge level: Half a Partner
I like: Cats; single malt Scotch; Stargate; Amiga; fried potatoes; retro gaming; cheese; snickers; sticky tape.
I don't like: Dimples in the bottom of scotch bottles; Facebook games masquerading as godgames.
Steam: stonelesscutter
GOG: stonelesscutter
|
Post by Lord Ba'al on Jul 19, 2014 13:57:34 GMT
My point was sort of about minimizing the amount of "real-time" calculations required by getting as much as possible pre-calculated while at the same time minimizing the amount of online data traffic required. Like I said there should be plenty of ways to cut corners which might speed up the process by a factor of 10^x. Come on guys, where is the can-do attitude?
|
|
|
Post by Danjal on Jul 19, 2014 14:34:55 GMT
My point was sort of about minimizing the amount of "real-time" calculations required by getting as much as possible pre-calculated while at the same time minimizing the amount of online data traffic required. Like I said there should be plenty of ways to cut corners which might speed up the process by a factor of 10^x. Come on guys, where is the can-do attitude? I think we left our "Can Do" attitude in the fiction section, and I do believe I saw Peter wandering around there aswell. I see where you're coming from, but when working within certain parameters you'll have to draw boundaries of what is realistically possible. Don't get me wrong, I'd love for these things to work. But given the restrictions given, you have to make choices. In this case the realistic choice would be to EITHER use tricks and go with a full on massive world with tons of people online *OR* go with a more elaborate system, but restrict it to local only play (perhaps some locally hosted online instanced matches inbetween). The scaling just wouldn't work. Why do so many elaborate resource management and strategy games limit themselves to local only while the more competative online variants try to keep things simple? It has very much to do with this same concept. Imagine for a second if EUIV or Civilization V did all the resource processing in realtime like Banished does. It'd scale out of control quickly (considering that the large Civ V maps are already taxing their system heavily and the modded larger maps are known to crash often). So at that point you have to make a choice, do you want your Jupitersize world? Or would you rather have more depth and complexity within your game? Or alternately, if you're gonna try both, where do you draw the line - where is your focus? Something that from outside observation seems to be lacking in the case of 22cans, because they've been going back and forth on statements claiming they literally want to do it all and satisfy everyone that likes each aspect. As such, rather than speculating some ideal vision and betting money on wishful thinking - it'd be better for everyone to set some realistic expectations and work from there. Granted, innovation rarely comes without taking some risks - but there are limits to taking risks aswell. Before taking such risks, it'd be wise to have atleast some reasonable expectation that what you're planning on doing can be done within a reasonable timeframe and budget.
|
|
splitterwind
Master
Posts: 149
I don't like: Ignoring a unpleasant question or answering with something that is only loosely related or way to vague to actually answer something. Mods that Cherry-pick in discussions. Banning people for minor offenses.
|
Post by splitterwind on Jul 19, 2014 15:04:09 GMT
My point was sort of about minimizing the amount of "real-time" calculations required by getting as much as possible pre-calculated while at the same time minimizing the amount of online data traffic required. Like I said there should be plenty of ways to cut corners which might speed up the process by a factor of 10^x. Come on guys, where is the can-do attitude? ;) You forget that even pre-calculation need a lot of time and moreso memory and storage. Also in a completly shapable environment heavy pre-calculating is a rather bad idea. It's simply not possible without coming up with a complete new approach that no one has considered before (good luck with that). By the way Pathfinding isn't solely a problem of gaming but also used in other software (commuting, gps navigation) and scientific problems. It's definitely not like nobody so far tried to optimize pathfinding...
|
|
|
Post by engarde on Jul 19, 2014 19:19:33 GMT
I could give a stuff what the size of relates to. I do not care to measure it. I just need a fully dynamic expanding world to cope with whatever minutes or hours I've put into it.
|
|
|
Post by Gmr Leon on Jul 21, 2014 19:55:31 GMT
This is why the cleverer approach to a problem like this is to do several things: - Not present in a technical fashion, but as all games are, a mixture of technical and aesthetic fashion.
- Find the engine constraints and then work within those constraints to make however large a map you think will be fun and stable, then build gameplay around that.
- Create a fluff reason for the inability to expand outside the range of these maps that masks the technical constraints, and take advantage of your artistic talent to convey those fluff reasons.
- Even better, turn those fluff reasons into a functional aspect of gameplay that does not overly tax the game engine and alternates the game mode, extending player influence outside the map but in a less zoomed in way. Retain depth, but reduce complexity through simplification, all inspired by recognizing the limitations of your resources.
It's the basic overworld solution to sewing together levels and different town hubs.
|
|
|
Post by neonero on Jul 23, 2014 10:24:22 GMT
There is also the aspect of calculation power of a smartphone. A smart phone doesn't have equal hardware to a PC. Also they have a limited battery, and should not run at max performance for extended periods of time.
So I believe a current generation smartphone won't be able to pathfind 1000+ people
And GODUS is a smartphone app.
The "PC" version is the mobile version running in an emulator.
|
|
|
Post by muumipeikko on Jul 31, 2014 15:36:27 GMT
Something very ironic struck me a few days ago while reading a book on the solar system to my Son. Peter keeps talking about Jupiter style world and I'm guessing like me he would have studied Astrophysics (maybe) and a time we didn't know that much and Pluto was still considered a planet...
I'd love to know if Peter realised that Jupiter while being the biggest planet in our solar system is a Gaseous planet, that is, a planet made up of nothing but hot air (or mostly hydrogen and helium in the case of Jupiter)? Was he having the ultimate laugh at us with this Jupiter idea or like many of us did he not realise what a gaseous planet was?
|
|
|
Post by Danjal on Jul 31, 2014 17:04:51 GMT
...I'm not sure to laugh or to cry - but that is FAR too close to the truth to be comfortable...
Jupiter Sized Planet - one hot air promise if we ever saw one.
|
|
Deleted
Deleted Member
Posts: 0
|
Post by Deleted on Jul 31, 2014 17:12:41 GMT
...I'm not sure to laugh or to cry - but that is FAR too close to the truth to be comfortable... Jupiter Sized Planet - one hot air promise if we ever saw one. Perhaps you're right. They have been going on a bit about their "cheeky teasers" lately. Maybe you've outed the grand-daddy of them all.
|
|
|
Post by 13thGeneral on Jul 31, 2014 18:15:48 GMT
Lol. Good question.
Jupiter's "core" is believed to be a non-solidified thick sludge of viscous material. Sounds familiar somehow...
|
|