Game Lag Tests

[hpongledd]

21 hours ago, DarkMoge said:

what do you mean? that is elementary. You can implement that under a day of work, depending on what you already have... Just writting the algorythm is like 2 hours at most. I do not think it would make any sense to use in oni though, with the rate of how often it changes the available paths.

As i said i dont understand a single word, but i can imagine that its easy stuff for a mathemitician and maybe implementing the function is trivial, but i can also copy paste a function into my code, useless **** but hey "i implemented the function" ;). Also i dont think you need two hours most. I dont understand a thing about it but the sole fact it was only google and a professor who wrote this algorithm i think it needs a little bit more then two hours but in case you really are that good, here waits a big business opurtinity for you (my former company would be more than happy to pay 1000 dollar/month if you can provide a better and more performant solution than they currently have, wanna have the contact? Not to talk about all the other taxi, deliver companies who are struggling with the exact same stuff)

ähhm ok, as i said i dont know anything about it, but  im a software developer and i guess calculating the best routes over a whole country, everytime an order comes in, with an average output of around ~10 order per minute is more cpu intense than the.... lets say retrigger a calculation over 20 possible routes every tick.

Therefore i concluded that you have exactly the same knowledge about the topic as i do. Ergo none.

edit: and not to forget you solve a an issue that a lot of mathematician are struggling with in "2hours most".

 

[kapoff]

Quote

lets say retrigger a calculation over 20 possible routes every tick

This point hurt me. I understand this is good for gameplay but honestly i would prefer this calculation happen... Lets say one time every second or two (maybe more) ?
My dupe will stuck in dead end ? So what he will back on the road later.
Don't think that will ruins the gameplay but for sure will boost performances.

Remember Factorio optimizations patches was done like that : less calculation intensive and less precise gameplay. But performance was here.

Sorry for my bad English

[Erasmus Crowley]

1 hour ago, hpongledd said:

As i said i dont understand a single word, but i can imagine that its easy stuff for a mathemitician and maybe implementing the function is trivial, but i can also copy paste a function into my code, useless **** but hey "i implemented the function" ;). Also i dont think you need two hours most. I dont understand a thing about it but the sole fact it was only google and a professor who wrote this algorithm i think it needs a little bit more then two hours but in case you really are that good, here waits a big business opurtinity for you (my former company would be more than happy to pay 1000 dollar/month if you can provide a better and more performant solution than they currently have, wanna have the contact? Not to talk about all the other taxi, deliver companies who are struggling with the exact same stuff)

ähhm ok, as i said i dont know anything about it, but  im a software developer and i guess calculating the best routes over a whole country, everytime an order comes in, with an average output of around ~10 order per minute is more cpu intense than the.... lets say retrigger a calculation over 20 possible routes every tick.

Therefore i concluded that you have exactly the same knowledge about the topic as i do. Ergo none.

edit: and not to forget you solve a an issue that a lot of mathematician are struggling with in "2hours most".

 

Pathfinding in general is very difficult and mathematicians struggle to find the best algorithm to solve it. 

Ant colony optimization is an algorithm, not the whole of the problem.

You are falsely accusing the person you responded to of claiming to solve all of the problems of pathfinding, which they never claimed to do.They were only talking about that one algorithm. It's not particularly difficult to implement as far as algorithms go. You're using a textbook strawman fallacy to try and make the other person look silly.

The reason you had so much trouble finding someone to copy/paste from is that ant colony optimization is very niche, not because it's hard. Dijkstra's algorithm or A* are almost universally chosen instead because they're better suited to game environments where quickly solving graphs that change often is required. For example, if you read the wikipedia article on pathfinding, ant colony optimization is not even listed as a potential solution.

You seem to be saying that if you can't understand something, then no one can possibly understand it. It's almost as if you automatically assume that you're the smartest person in any group that you're in. That's a very naive and narcissistic perspective, and I don't think it holds up to any level of scrutiny at all. I find it kind of distasteful actually.

[hpongledd]

20 hours ago, Erasmus Crowley said:

You are falsely accusing the person you responded to of claiming to solve all of the problems of pathfinding, which they never claimed to do.They were only talking about that one algorithm. It's not particularly difficult to implement as far as algorithms go. You're using a textbook strawman fallacy to try and make the other person look silly.

Lovely. Its called trolling and playing with words. Beside that it should go without saying that the part i find hard its not implementing the algorithm but rather using in a "real environment". Theory is a nice thing but unfortuntely i never studied in my life and im more of a idealistic/pragmatic person.

Quote

The reason you had so much trouble finding someone to copy/paste from is that ant colony optimization is very niche, not because it's hard. Dijkstra's algorithm or A* are almost universally chosen instead because they're better suited to game environments where quickly solving graphs that change often is required. For example, if you read the wikipedia article on pathfinding, ant colony optimization is not even listed as a potential solution.

I never talked about game environments, did i? But yeah, i'll give you that one, since you are right, i guess

Quote

You seem to be saying that if you can't understand something, then no one can possibly understand it. It's almost as if you automatically assume that you're the smartest person in any group that you're in.

I seem to be saying, that i never carred enough to deep dive into the topic and to get a feeling how programming somehting like that in a real case scenario is. So if someone says "its not that difficult", he should maybe consider the implementation in a real case scenario not some "proof of algorithm" solution. Im smart enough to realize that i also need two hours to create a console application, copying an algorithm into it and maybe an input for start/destination, but where is the benefit of this for a real case scenario?

Quote

That's a very naive and narcissistic perspective, and I don't think it holds up to any level of scrutiny at all. I find it kind of distasteful actually.

I tend to be arrogant while trolling. But a quick search on google brought me to a bachelor degree thesis called "UTILIZING SWARM INTELLIGENCE ALGORITHMS FOR PATHFINDING IN GAMES"

Without reading the whole paper, i'll just quote this part from the Summary:

Quote

Results of the experimentation indicatedthat the SI algorithms both were capable of determining a path at a greater speed than the A* algorithm.The ACO algorithm was capable of determining an initial path at a greater speed than the A*algorithm. This is a result of the fact that A* opts to determine the shortest path whereas ACO merely determines a path. After having calculated an initial path the ACO algorithm was proven to be capable o fdynamically updating its path at a greater speed than the A* algorithm could recalculate a path. The difference in path calculation times proved greater on maps with a greater amount of smaller sized obstacles.

To remain fair, as far as i understood, his conclusion is ACO is faster at calculating but less optimal paths were taking. Also to under some circumstances calculations were faster with A*. So....my trolling holds up, to some degree, to a 5min scrutiny.

Regarding using ACO for ONI: His tests were made with an 512x512 grid sized map. If i recall correctly ONI maps are smaller? SI path calculation tends to be becoming slower with the ratio of obstacles increasing.

As far as im concerned i would say the trade off less optimal paths for faster performance is acceptable and could be a better solution for ONI, if someone would run tests to check at which rate of obstacles A* and ACO will have equal speed, based on this number ACO could provide more value.

Only because A* is the "standard" it doesnt mean its the best option and also only because ACO isnt mentioned as a possible solution on your wikipedia list it doesnt mean it cant be one, ever heard about "thinking outside of the box"?

The statement of my intial post was "Klei wont do anything about it, because they dont have a ******* clue either, elsewise someone would have done it, a long time ago." Another reason could be (probably more realistic) that they can but wont because its not worth it. Why? It costs them a lot of resources and the benefit is, lets generously say, 10% of the player base will have better frame rates on their big bases. Therefore, i think its only fair, if i troll back isnt it? Its the same kind of discussion we had a couple of months ago where R9MX4 (or whatever his name was ragequitted the forum because Klei did not thread him right and ignored all of this wonderful exploits of bugs he made, displaying serious issues with the game. (for the ones that think this is sarcasm, it isnt. I truely admire what he did for the community and Klei, he has my respect). But damn son get a grip and keep your **** for yourself. Klei is serving 1.5 Millions Players, not only those 30 narcisstics persons that love ONI and get offended if Klei doesnt say "Thank you!" everytime they post a sophisticated bug which only appears with deep game knowledge.....And in the end, maybe for game developers this one is less true, its all about money, they wanna make money, period. They dont care about you, me or the whole community. The handle our **** because they know, we give them money, therefore they need us to pay the bills and we need them for our entertainment.

Or would you say those conclusions/assumptions are wrong? 

But again, please remember: i dont have a ******* clue about what im talking ;D

edit: god....im enjoyiing this way too much....

 

[bobucles]

20 hours ago, Erasmus Crowley said:

Ant colony optimization is an algorithm, not the whole of the problem.

But why would you need that algorithm? We're not dealing with travelling salesmen here. We're dealing with dupes who can only handle one task at a time, and only need to consider one singular future task when the current one is finished.

Commute times destroy dupe efficiency, so choosing tasks with short commute times is generally a pretty good solution. The current job system has a lot of "round trip" tasks. Dupes choose a job nearby, but the job involves grabbing a material far a way and running back. That's a guaranteed 2 trips for every job, which is very BAD on commute time and obviously requires more processing under the hood as well. Choosing singular path jobs is faster not only for dupes but simplifies the problems the game has to solve as well.

A dupe may be near junk so they run it to storage, then they're near storage so they run materials to machines, now they're near machines so they run the machines. It's a very opportunistic job system that keeps dupes busy doing useful things with less random running.

[hpongledd]

43 minutes ago, bobucles said:

Commute times destroy dupe efficiency, so choosing tasks with short commute times is generally a pretty good solution. The current job system has a lot of "round trip" tasks. Dupes choose a job nearby, but the job involves grabbing a material far a way and running back. That's a guaranteed 2 trips for every job, which is very BAD on commute time and obviously requires more processing under the hood as well. Choosing singular path jobs is faster not only for dupes but simplifies the problems the game has to solve as well.

I think you are simplifying too much here. From a job perspective its a guaranteed 2 trips, from a task perspective its 1 trip per task. Pathfinding doesnt know about the whole job stuff, so it will treat everything as 1 trip. The job perspective can be brought in by Klei and be considered for calculation, but we are talking about top level archtiecture here. Something that had to be decided at the beginning of the project. If they choose another approach, changing it will be close to impossible. I dont know which parameter Klei choose to be dependent on for path calculations. I hope the people arguing know what Klei choose.

Quote

A dupe may be near junk so they run it to storage, then they're near storage so they run materials to machines, now they're near machines so they run the machines. It's a very opportunistic job system that keeps dupes busy doing useful things with less random running.

Again, simplified to a point its not practiable anymore. For example: a dupe is standing on a tile where a low priority task is, but two tiles away there is a high priority task. Which one should now be choosed? Ok, you could say "pick the highest priority task in a range of 8 tiles". Problem solved. Now, 9 tiles away there is a high priority task, 3 tiles away there is a low pririty task. This  low priority task happens to be storing, which include walking to a storage container, maybe 30tiles away. do you recalculate the possible options when you are at the low pirioty task tile or do you execute it nonetheless? Questions, questions, questions, trade offs to take a lot of not foreseen situations, which raise another cople of questions and another buch of trade offs. Maybe a travelling salesman approach wouldnt be that bad. SInce you can calculate what it would cost me solving a low priority task before a high level task and if its more worth doing the high priority task first.

 

[DarkMoge]

9 hours ago, hpongledd said:

Theory is a nice thing but unfortuntely i never studied in my life

That is why you are being impressed by small simple things.To prove how simple it is, it was easily used by a bachelor in their thesis... But, I guess, for someone uneducated that sounds impressive. ~ ♪

 

9 hours ago, hpongledd said:

I seem to be saying, that i never carred enough to deep dive into the topic and to get a feeling how programming somehting like that in a real case scenario is. So if someone says "its not that difficult", he should maybe consider the implementation in a real case scenario not some "proof of algorithm" solution. Im smart enough to realize that i also need two hours to create a console application, copying an algorithm into it and maybe an input for start/destination, but where is the benefit of this for a real case scenario?

I gave an estimate for likely time that you would require to implement it. Not to copy paste it. To implement something, I consider that you already have all the required elements to make it work, in case of the pathfinding, you need some sort of a map with set movement rules that you can pass as an argument to the pathfinding algorithm. Implementing even a basic map takes longer than to actually implement that algorithm.

There are some basic procedures that developers follow. If there is a map, than there is some sort of _GetMap() function and there is an example of how the data will be presented. And after you finish implementing algorithm, you create some sort of _GetPath() for the next part of your project. The path is than handled by rendering engine that moves your units every tick according to the data it have received. You should have a pretty good idea in what format does it expect that data.

What is confusing you is probably your own expectations. An algorithm is not a task to be solved, it is a solution for the task. So, applying it in real environment is not hard... It is like math, you have formulas that provide you with solutions for your task. You will run into problems when you are trying to force a wrong formula as a solution for something. Or, you are trying to invent something new... Inventing things takes way more effort than realizing inventions.

 

9 hours ago, hpongledd said:

To remain fair, as far as i understood, his conclusion is ACO is faster at calculating but less optimal paths were taking. Also to under some circumstances calculations were faster with A*. So....my trolling holds up, to some degree, to a 5min scrutiny.

Regarding using ACO for ONI: His tests were made with an 512x512 grid sized map. If i recall correctly ONI maps are smaller? SI path calculation tends to be becoming slower with the ratio of obstacles increasing.

As far as im concerned i would say the trade off less optimal paths for faster performance is acceptable and could be a better solution for ONI, if someone would run tests to check at which rate of obstacles A* and ACO will have equal speed, based on this number ACO could provide more value.

Here is a problem with that idea, if you realized how the ACO actually works, you would know that its speed is not determined by the grid size, but by the number of points of interest. It attempts to create a floating data that helps to find more and more optimal path from one point of interest to another.
When we talk about ONI, it happens to be that the number of points of interest easily ends up being even higher than total number of cells on the map. If we limited points of interest to things like toilets and beds and recreational room than maybe, but for ONI, every single resource lying on the ground is a separate point of interest and every single construction order of which we can have like 6 in the same block(tile+gas pipe+water pipe+wire+automation wire+coveyer belt, not to mention bridges built over it)... To make matters worse, the points of interest keep on dynamically changing through the game, which means is that ACO will harm our attempts to find an optimal path... You see, ACO tries to store a floating data how to get to a point of interest and when something stops being a point of interest, the floating data about getting to it would take some time to deteriorate. To make the matter even worse, the available paths keep changing in the game... So, when you build a wall, the floating data about there not being a wall before and it being a good path before will remain. In practice, that means dupes would run to the dead end walls and back when they are trying to get somewhere.

9 hours ago, hpongledd said:

Only because A* is the "standard" it doesnt mean its the best option and also only because ACO isnt mentioned as a possible solution on your wikipedia list it doesnt mean it cant be one, ever heard about "thinking outside of the box"?

It makes so much sense for you to talk about an algorithm that you do not understand and claim that using it as a solution for this problem is "thinking outside of the box". What if you are trying to apply wrong solution to the problem.

9 hours ago, hpongledd said:

The statement of my intial post was "Klei wont do anything about it, because they dont have a ******* clue either, elsewise someone would have done it, a long time ago.

Things do not actually work that way... You assume that if there is a problem and someone can solve that problem than they would have already solved it.

Here is a situation that would be easy to simulate. Find a room with multiple people in it, a trash can and a piece of trash somewhere in the middle of the room... Everyone has an ability to pick up that trash and throw it into the trash can... And it is something that needs to be done. There can be multiple reasons why no one did it yet.

I do not want to make too many assumptions about you, but probably... you have a bunch of unwashed dishes at the kitchen which you are just letting to pile up.

Problems do not resolve themselves, because someone can solve them, they are resolved when someone actually decides to solve them.

You could be pragmatic and attempt to calculate the benefit ratio to the effort ratio... But there are more possible cases... In my eyes, klei is a small indie company that wants to make many wonderful games. Optimizing code is a pretty boring thing to do, I do not think any programmer wants to dig through their code to try and optimize it after it is done. And when you think about the idea of "making wonderful games" it is a pretty enjoyable thing to do, but when you think about optimizing them, it sucks...

Try writing a story, you will find it much easier to write a story than going through the story you have written and trying to fix all of your grammar errors and trying to come up with better words to express same things.

8 hours ago, hpongledd said:

I think you are simplifying too much here. From a job perspective its a guaranteed 2 trips, from a task perspective its 1 trip per task.

Oni actually happens to be more of 1 trip per task. Dupes do not return to their starting position after they complete a task, instead, they move towards the next one. And a lot of task usually only need to be done once. I believe, that at least 90% of the dupes tasks are not routine. All routine tasks end up being handled by players by building automation.

8 hours ago, hpongledd said:

Again, simplified to a point its not practiable anymore. For example: a dupe is standing on a tile where a low priority task is, but two tiles away there is a high priority task. Which one should now be choosed? Ok, you could say "pick the highest priority task in a range of 8 tiles". Problem solved. Now, 9 tiles away there is a high priority task, 3 tiles away there is a low pririty task. This  low priority task happens to be storing, which include walking to a storage container, maybe 30tiles away. do you recalculate the possible options when you are at the low pirioty task tile or do you execute it nonetheless? Questions, questions, questions, trade offs to take a lot of not foreseen situations, which raise another cople of questions and another buch of trade offs. Maybe a travelling salesman approach wouldnt be that bad. SInce you can calculate what it would cost me solving a low priority task before a high level task and if its more worth doing the high priority task first.

Pretty sure that is a bad way to look at this. It would be much more practical to have an array of tasks that are ordered by their priority and an array of dupes... You cycle through the list of task with every dupe, looking only at the higher priority tasks and than you select the task with the lowest distance and remove it from the list. I feel like 80% confident that it is what ONI actually does. We have proofs in the form that dupes will actually run towards doing higher priority task regardless of the distance and that they get nothing done when there are too many tasks at same priority. This method actually starts failing when there are many tasks at same priority, but it is superior for pretty much always inside ONI environment.

A problem of task distribution between dupes is actually pretty similar to the problem of pathfinding. But the idea of ACO would not help there.

Where the idea of of ACO could help is help dupes find their bed, mess table, toilet, shower. But you might still end up being slower than just calculating it with A*... Why? Because, it is a different type of a point of interest... You would need to store a separate array for each or your dupes would end up running to their bed when looking for toilet. Also, it is a different one for each dupe, so you would need separate arrays for each dupe. Running 256*384 sized map with 50 dupes on it and 5 different goal types to look for would create 187.5 mb of floating data in your operative memory that could be used for something else. When reaching those specific points of interest is actually not urgent as the game has most of the cycle dedicated to calculating only those paths. And when downtime is over, you would still have that 187.5 mb floating in your memory for no reason. Not to mention, the whole thing would become slower than A* when the player relocates those points of interest.

On 9/5/2019 at 6:09 PM, hpongledd said:

my former company would be more than happy to pay 1000 dollar/month

programmers are paid way more than that. https://www.daxx.com/blog/development-trends/it-salaries-software-developer-trends-2019