AI pathfinding of creatures still not fixed?

[archblue1206]

the pigs still walk straight to the wall like its not even there...and keep yelling "home home":ambivalence:

[Snob]

The AI is still being worked on, be patient!Maybe the next update probably has some tweaks regarding the pathfinding AI.

[archblue1206]

oh ok...i just hate it when the pigs get stuck on my base then transforms then whacks all my walls..

[Moonkis]

Well, considering that Pathfinding is pretty expensive in terms of CPU cycels they have most likely done some shortcuts here and there to avoid pathfinding every frame, specially considering it's an 3D game. ( Kevin, I'm assuming here so don't be an jerkwad about it )I'm guessing they are doing an raytrace in an straight line from Player and ObjectX that is following you, when there is an collision in that line they are most likely doing an proper A* pathfinding.

[archblue1206]

Well, considering that Pathfinding is pretty expensive in terms of CPU cycels they have most likely done some shortcuts here and there to avoid pathfinding every frame, specially considering it's an 3D game. ( Kevin, I'm assuming here so don't be an jerkwad about it )I'm guessing they are doing an raytrace in an straight line from Player and ObjectX that is following you, when there is an collision in that line they are most likely doing an proper A* pathfinding.

uhmmm,so no?

[Moonkis]

uhmmm,so no?

The implementation they are using covers MOST cases pretty well, but there are bound to be some cases that isn't covered, they will most likely hack something together, in other words, it's not fully done yet.

[Avarice]

Translated: He thinks they used a cheap shortcut that doesn't always work and might fix it later.

[Kevin]

Only short-range pathfinding is implemented at present, for performance reasons. Once a certain length of path is reached, the search algorithm gives up and defaults to the old "run straight at it" method. You mostly see this when creatures with homes are trying to return at night, because they can get pretty far away during a day.We're looking into putting in a hierarchical system to allow for longer pathfinds. We weren't sure how y'alls computers would handle the increased load, so we're rolling out new features slowly. Also, it takes a while to implement, and Brook (our pathfinding expert), is busy making walrusser behaviours this week.

[archblue1206]

The implementation they are using covers MOST cases pretty well, but there are bound to be some cases that isn't covered, they will most likely hack something together, in other words, it's not fully done yet.

the follower pigs are great though..

[archblue1206]

Only short-range pathfinding is implemented at present, for performance reasons. Once a certain length of path is reached, the search algorithm gives up and defaults to the old "run straight at it" method. You mostly see this when creatures with homes are trying to return at night, because they can get pretty far away during a day.We're looking into putting in a hierarchical system to allow for longer pathfinds. We weren't sure how y'alls computers would handle the increased load, so we're rolling out new features slowly. Also, it takes a while to implement, and Brook (our pathfinding expert), is busy making walrusser behaviours this week.

thanks for the reply kevin!appreciate it...yeah,i also think it would be a big load if every creature would have longer pathfinds..but it would surely be great...oh and please give my thanks to brook for making the follower pigs smarter..:applause:WAIIIIIIIIT!!!,walrusser?the hunting party of father and son?gawd!i want them!!!! Edited February 20, 2013 by archblue1206

[DBM]

Only short-range pathfinding is implemented at present, for performance reasons. Once a certain length of path is reached, the search algorithm gives up and defaults to the old "run straight at it" method. You mostly see this when creatures with homes are trying to return at night, because they can get pretty far away during a day.We're looking into putting in a hierarchical system to allow for longer pathfinds. We weren't sure how y'alls computers would handle the increased load, so we're rolling out new features slowly. Also, it takes a while to implement, and Brook (our pathfinding expert), is busy making walrusser behaviours this week.

I am still seeing the 'run straight at it' thing with pigs who are an inch or two from their home, with a fence between them and the house (with a gap in it). Does it cut off when they go into Run Home mode?

[Moonkis]

Only short-range pathfinding is implemented at present, for performance reasons. Once a certain length of path is reached, the search algorithm gives up and defaults to the old "run straight at it" method. You mostly see this when creatures with homes are trying to return at night, because they can get pretty far away during a day.We're looking into putting in a hierarchical system to allow for longer pathfinds. We weren't sure how y'alls computers would handle the increased load, so we're rolling out new features slowly. Also, it takes a while to implement, and Brook (our pathfinding expert), is busy making walrusser behaviours this week.

Oh, I guess I was pretty far from your implementation then? I know this isn't an universal solution, but you guys are threading the pathfinding, right?EDIT:Consider this, even if the question is "n00bish" in the sense that "of corse we thought of that" it's still very entertaining to an official answer wich explains the inner workings. I mean ( and take this the right way ) you guys are very experienced but if being blunt and honest we both know that there are very few programmers that program 100% flawless code/design, you are bound to have compromised somewhere Edited February 20, 2013 by Moonkis

[Moonkis]

Translated: He thinks they used a cheap shortcut that doesn't always work and might fix it later.

Eh, well that is one way to put it, but most games are cutting corners, using herichal A* ALL the time on everything expensive, expecially if there is a lot of objects that uses it, and in Don't Starve there is a lot, look at Age of Empires I & II series for example, or how Rachet and Clank if you want something modern.

[Kevin]

There may be something specifically broken about the go-home behaviour. I'll mention it to Brook. It may just be that the path around the barrier is too long, or maybe something is wrong with the early-out line of sight test that also circumvents the pathfinder.Threads are tricky, on account of our monolithic lua state. The pathfinding is done on the engine side, so it would be possible. Of course, it won't help on the machines that need the speed boost the most, because they are single-core toasters running the Chrome version.Trying to make a PC game with a low minspec can be frustrating sometimes, because all of the best solutions only help machines that are already running the game well :)We haven't spent a heck of a lot of time on optimization yet. We've only done the bare minimum on an as-needed basis based upon forum reports. It's actually hard to buy a new (non-netbook) computer that doesn't run the game well, so unless we go dumpster diving it's hard to replicate a lot of problems in-house.

[Avarice]

The only time I see the pigs stuck is when they are going home and it's usually against the edge of the world near the water...where all things have always become stuck.

[Moonkis]

There may be something specifically broken about the go-home behaviour. I'll mention it to Brook. It may just be that the path around the barrier is too long, or maybe something is wrong with the early-out line of sight test that also circumvents the pathfinder.Threads are tricky, on account of our monolithic lua state. The pathfinding is done on the engine side, so it would be possible. Of course, it won't help on the machines that need the speed boost the most, because they are single-core toasters running the Chrome version.Trying to make a PC game with a low minspec can be frustrating sometimes, because all of the best solutions only help machines that are already running the game well :)We haven't spent a heck of a lot of time on optimization yet. We've only done the bare minimum on an as-needed basis based upon forum reports. It's actually hard to buy a new (non-netbook) computer that doesn't run the game well, so unless we go dumpster diving it's hard to replicate a lot of problems in-house.

Sure! I'm guessing something along the lines of using an spartial-tree as an grid , and running raytracing before ( Even though Raytracing is expensive it is bound to be less expensive than A* finding ) using H. A* would be part of the optimisation, or make them run straight towards the player and then do an pathfinding when the next step would inflict an collision and they still aren't near the player?Ugh, I guess time will tell, but please do tell once you optimized it!

[DBM]

I took this picture cause of the awesome fire. but the grass fence that is burning is the one my pigs got stuck on in 'go home mode' so it shows the sort of distance I am talking about.

[Kevin]

Were the pigs on the left hand side of the screen? If that's the case they were probably too far away along the path. I'll show it to Brook. He'll probably just furrow his brow and resume working on walrusser :)I feel sorry for that poor shadow hand. He really doesn't have his priorities sorted.

[ImStarving]

I feel sorry for that poor shadow hand. He really doesn't have his priorities sorted.

Seriously, that shadow hand is suffering from tunnel vision in that picture.

[DBM]

Were the pigs on the left hand side of the screen? If that's the case they were probably too far away along the path. I'll show it to Brook. He'll probably just furrow his brow and resume working on walrusser :)I feel sorry for that poor shadow hand. He really doesn't have his priorities sorted.

Yes from the left - BUT - there were gaps in the fence to let them in and out (on the left).

[Brook]

Well, considering that Pathfinding is pretty expensive in terms of CPU cycels they have most likely done some shortcuts here and there to avoid pathfinding every frame...

Very true!

I'm guessing they are doing an raytrace in an straight line from Player and ObjectX that is following you, when there is an collision in that line they are most likely doing an proper A* pathfinding.

Close, but since the game world is build on a grid, we can actually skip the raytrace and just step along the grid checking each one to see if it is either impassable (eg. water) or contains walls. If so, we do a proper pathfind. (Objects that are not walls are completely ignored for pathfinding purposes at the moment)

However, as already mentioned:

[*]We only pathfind over short distances, if it's more than about a screen away, we don't bother as it becomes more likely to be too expensive.

[*]Even if it's a short distance, and even if it look to you as though there is an obvious path, it's still possible for A* to take quite a few steps to find the path... so this is also limited. Basically we let the A* pathfinding run for a while, and if it hasn't found a path by then, we cancel the operation because we have to get on with running the rest of the game.

Two likely additions will address these later are hierarchical pathfinding, which will make it much more practical over long distances; and queuing up the pathfind to occur over several frames, instead of requiring it to complete either all or nothing in a single step, which would allow even very long paths to be computed (hopefully) without grinding your game to a halt.

We just need to budget the time to do those things

*furrows brow*

*goes back to making an igloo*

[BarovSoap]

Lies, all lies! Brook is working with Kevin! Everyone knows Don't Starve doesn't have igloos...(hint hint)

[Excess]

He'll [brook] probably just furrow his brow and resume working on walrusser

*goes back to making an igloo*

Winter is coming + Walruses + Igloos...

...I like where this is going.

[archblue1206]

troll ninja!

- - - Updated - - -

The only time I see the pigs stuck is when they are going home and it's usually against the edge of the world near the water...where all things have always become stuck.

they also get stuck when they see food like seeds inside your base!

[BarovSoap]

Winter is coming + Walruses + Igloos......I like where this is going.

Don't believe the lies!