Thrive Game Development

Development of the evolution game Thrive.
 
HomeHome  PortalPortal  CalendarCalendar  FAQFAQ  SearchSearch  MemberlistMemberlist  UsergroupsUsergroups  RegisterRegister  Log inLog in  
Welcome new and returning members!
If you're new, read around a bit before you post: the odds are we've already covered your suggestion.
If you want to join the development team, sign up and tell us why.
ADMIN is pleased to note that this marquee has finally been updated.
ADMIN reminds you that the Devblog is REQUIRED reading.
Currently: The Microbe Stage GUI is under heavy development
Log in
Username:
Password:
Log in automatically: 
:: I forgot my password
Quick Links
Website
/r/thrive
GitHub
FAQs
Wiki
New Posts
Search
 
 

Display results as :
 
Rechercher Advanced Search
Statistics
We have 1675 registered users
The newest registered user is dejo123

Our users have posted a total of 30851 messages in 1411 subjects
Who is online?
In total there are 2 users online :: 0 Registered, 0 Hidden and 2 Guests :: 1 Bot

None

Most users ever online was 443 on Sun Mar 17, 2013 5:41 pm
Latest topics
» THIS FORUM IS NOW OBSOLETE
by NickTheNick Sat Sep 26, 2015 10:26 pm

» To all the people who come here looking for thrive.
by NickTheNick Sat Sep 26, 2015 10:22 pm

» Build Error Code::Blocks / CMake
by crovea Tue Jul 28, 2015 5:28 pm

» Hello! I can translate in japanese
by tjwhale Thu Jul 02, 2015 7:23 pm

» On Leave (Offline thread)
by NickTheNick Wed Jul 01, 2015 12:20 am

» Devblog #14: A Brave New Forum
by NickTheNick Mon Jun 29, 2015 4:49 am

» Application for Programmer
by crovea Fri Jun 26, 2015 11:14 am

» Re-Reapplication
by The Creator Thu Jun 25, 2015 10:57 pm

» Application (programming)
by crovea Tue Jun 23, 2015 8:00 am

» Achieving Sapience
by MitochondriaBox Sun Jun 21, 2015 7:03 pm

» Microbe Stage GDD
by tjwhale Sat Jun 20, 2015 3:44 pm

» Application for Programmer/ Theorist
by tjwhale Wed Jun 17, 2015 9:56 am

» Application for a 3D Modeler.
by Kaiju4u Wed Jun 10, 2015 11:16 am

» Translator to Serbian here
by Simeartherist Sun Jun 07, 2015 6:36 am

» Presentation
by Othithu Tue Jun 02, 2015 10:38 am

» Application of Sorts
by crovea Sun May 31, 2015 5:06 pm

» want to contribute
by Renzope Sun May 31, 2015 12:58 pm

» Music List Thread (Post New Themes Here)
by Oliveriver Thu May 28, 2015 1:06 pm

» Application: English-Spanish translator
by Renzope Tue May 26, 2015 1:53 pm

» Want to be promoter or project manager
by TheBudderBros Sun May 24, 2015 9:00 pm


Share | 
 

 Pathfinding Antipatterns

View previous topic View next topic Go down 
AuthorMessage
moopli
Developer


Posts : 318
Reputation : 56
Join date : 2013-09-30
Age : 21
Location : hanging from the chandelier

PostSubject: Pathfinding Antipatterns   Sun May 18, 2014 12:32 pm

So, while waiting for thrive to compile I was reading through the old AI threads floating around, and I noticed a worrying trend.

Whenever the question of pathfinding comes up, the answer is usually something like A* over navmeshes. Now, there's nothing wrong with an agent doing A* over a navmesh. But what about when you have thousands of agents, each doing it's own A*? Then you have an issue; loads of stuff will get recalculated per-agent. I know, I know, you'll tell me we can just cache A* results, but then we get an overcomplicated Floyd-Warshall.

So let's say we generate a navmesh and Floyd-Warshall over it every frame. Now, agents are given the shortest path to their chosen target for free. Ofc, this solution isn't optimal: first off, if you don't have a high enough agent density your complexity just shot up. More importantly, however, is another massive inefficiency -- we may no longer be recalculating paths per-agent, but we're still recalculating all paths every frame. That's almost as bad -- in general, the environment changes incrementally per-frame, and a pathfinder that can't take advantage of the repetition is in trouble.

"But moopli!" says my strawman, "I call bullgium! There can't possibly be an incremental, non-agent-based pathfinding technique that gives us the power we need!", to which I say Pah!

Assuming you have read the paper, here are some more reasons i have to support this method:

  • It works well with the ECS -- A system can manage all the diffusion fields, and entities which need to follow certain gradients can register appropriate components.
  • It is scientifically accurate, at least for the Microbe stage and organisms relying heavily on scent -- it uses a diffusion model to set up the concentration gradients that agents then climb. For example, adjusting diffusion-particle decay rate can result in scent trails.
  • It models time lag in information-getting, decision-making, and more -- useful for strategy mode, where it can lead squads to make understandable mistakes in navigation (not knowing that their target has moved, perhaps). One hallmark of realistic-seeming AI is that it makes reasonable mistakes, the sort of mistake you'd expect from something intelligent.
  • It easily affords simple tactics with no overhead -- the paper demonstrates flanking maneuvers, for one.


One important implementation detail I'm doing some thinking about is the topology of the underlying graph that all the diffusion and pathing is done over. In the paper, all these graphs are regular grids, which really simplifies their implementation but has what might be troublesome overhead on larger spaces. The first solution I could think of is to diffuse over navmeshes, but that runs into issues when you want scent information at a higher resolution than navmesh polygons give you -- improving the performance of one hurts the other, and of course, we'd need to actually dynamically generate and modify the navmeshes without introducing ugly artifacts (but that borders on OT). The other I came up with is to store the gradient data in a quadtree (or an oct-tree when absolutely necessary). This way, we can adjust resolution as we need it.

Longpost is long, thanks for reading!

Edit: Is this the right place for this? I used a greedy approach to find the right subforum, but this forum is all over the place so I'm not sure if greedy works here...

Edit2: Elsewhere,
NichderNich wrote:
The ultimate goal will be to have compounds exist in particle clouds that float around and spread in your environment, like droplets of ink in water.
As a bonus this could also be implemented as part of the diffusion system, and it would feed seamlessly into pathfinding. Yay science!


Last edited by moopli on Sun May 18, 2014 12:42 pm; edited 2 times in total (Reason for editing : inspiration strikes again)
Back to top Go down
View user profile
crovea
Programming Team lead


Posts : 310
Reputation : 59
Join date : 2013-10-07
Age : 26
Location : Denmark

PostSubject: Re: Pathfinding Antipatterns   Sun May 18, 2014 12:58 pm

An amusing way of writing

Looks interesting, but you mention the microbe stage for which I don't see ay need for pathfinding as there is no other obstacles than other microbes, which can reasonably brute force past each other or have some reactionary system.

Naturally it could potentially become useful in the later stages. However a quick read through the pacman example seems to suggest that it is best used for multiple entities working towards a shared goal, while I suspect the needs of our future solutions will involve many entities with many distinct goals. Of course an A* or any other solution I can think of, doesn't solve the optimization of these issues either, but it seems to me that the concept deflates in the situation with multiple goals. Correct me if I misunderstand.

_________________
- jjonj on github/reddit, jjonjex/Jacob Jensen on skype
Back to top Go down
View user profile
moopli
Developer


Posts : 318
Reputation : 56
Join date : 2013-09-30
Age : 21
Location : hanging from the chandelier

PostSubject: Re: Pathfinding Antipatterns   Sun May 18, 2014 2:04 pm

Thanks, I do try

For microbes, this is more of a case of turning a simple representation of nutrient levels into a convenient pathfinder, by copying nature directly.

In many cases, we may have many interchangeable goals. For example, there will be many bits of fruit within reach of our monkey' (read: monkey-prime), and any piece will do, so monkey' goes for the closest. Then, if we have quite a few monkey' (our first one was quite prolific), they'll all want fruit, but any fruit will do. Since fruit are interchangeable, we can use the same diffusion graph for each piece of fruit. As a side bonus, several pieces of fruit far away could be more appealing than one fruit slightly closer but on the other side of monkey' -- making monkey' appear to plan ahead even though all it does is follow its nose.

We can even merge some non-interchangeable goals, for example, if the value of goal type A is a constant multiple of that of goal types B, C, and D, then it would simplify matters greatly to just use one field and have sources of differing strength.

As for dealing with distinct, possibly-conflicting goals, (that is, non-constant multipliers) this deflates. Then, the best we can do (I think?) is to reduce the set of necessary distinct fields (for example, instead of having separate fields for pathing towards the enemy and fleeing from battle, we could use one "danger" field, where fleeing units simple go down the gradient instead of up), and to reduce overhead by storing several diffusion types in one graph (among other optimizations, anyway).

We may be able to treat special cases where A* or something else is necessary as modified forms of the diffusion-gradient system, though I'd consider that more of an academic exercise.
Back to top Go down
View user profile
crovea
Programming Team lead


Posts : 310
Reputation : 59
Join date : 2013-10-07
Age : 26
Location : Denmark

PostSubject: Re: Pathfinding Antipatterns   Sun May 18, 2014 2:16 pm

I feel it would be too computationally expensive for the simple needs of the microbe stage, altough I can see some appeal.

For later stages, I think we'll have to wait and see what our fruits look like, if the organisms will make do with just bananas or if they'll want a full fruit basket with veggies too!

_________________
- jjonj on github/reddit, jjonjex/Jacob Jensen on skype
Back to top Go down
View user profile
moopli
Developer


Posts : 318
Reputation : 56
Join date : 2013-09-30
Age : 21
Location : hanging from the chandelier

PostSubject: Re: Pathfinding Antipatterns   Sun May 18, 2014 6:20 pm

I guess I just see more appeal than you perhaps

On the contrary, microbe stage would most likely have the simplest, and most useful diffusion system. We could simply use the compounds spawned in the environment to increment the cells nearby  -- so we get the particles, which are the most intensive part of the simulation, for free. Then just do a pass -- cheap when we'd only be simulating about 500 grid cells at a time -- enough for more than double screen space when each grid cell is about a cell big (nope not ambiguous at all nope) -- where we apply a blur and decay. And to pathfind we'd just let each cell (not grid, but swimmy) decrement the compounds under them and hill-climb.

We could even go all the way and store free-floating compounds in the grid, but I won't belabor the point as I'd rather see the game released

For later stages we'll definitely wait -- actually, I had the urge (now suppressed) to ask a mod to lock this until its time arrives


Last edited by moopli on Sun May 18, 2014 6:21 pm; edited 1 time in total (Reason for editing : bortle)
Back to top Go down
View user profile
Seregon
Regular


Posts : 263
Reputation : 37
Join date : 2011-08-10
Location : UK

PostSubject: Re: Pathfinding Antipatterns   Mon May 19, 2014 12:29 pm

Some very nice suggestions in there moopli.  I agree that we won't need anything partiularly advanced until atleast the aware stages, as the environments will be very simple (with few, if any, imovable obstacles).

I think A* came up as a suggestion mostly because its the one most people are familiar with.  As we're a long way from actually needing pathfinding the discussion never got much further.  I've always thought we'd go with a mixture of boids style movement, possibly with diffusion maps for finding direction to the nearest food/shelter etc.

What your suggesting sounds like a more advanced way of calculating diffusion maps, which may be useful, so I'll try and have a proper read of the paper when I get the chance.

One consideration is that we probably won't have very many agents simulated at the same time.  Due to the computational expense of AI, pathfinding, the compound system, and everything else we hope to simulate, only those agents relatively close to the player will be fully simulated (something like 1-200 agents at most).  Those agents outside the players areas will be vastly simplified, and probably won't need any pathfinding at all (they will either not have a tracked position, or be allowed to ignore obstacles).
Back to top Go down
View user profile
moopli
Developer


Posts : 318
Reputation : 56
Join date : 2013-09-30
Age : 21
Location : hanging from the chandelier

PostSubject: Re: Pathfinding Antipatterns   Mon May 19, 2014 10:34 pm

Thanks!

One of the more interesting things this could model -- which, methinks, would work best in Microbe stage -- is agents pathing away from resources if there's enough competition. That is, since microbes decrease the desirability of cells they've inhabited, a microbe between J. Random AI Microbe and some food might cause J. Random AI Microbe to go looking for fresher pastures. It isn't so much that we can solve the problem of getting from A to B, the trick is that by letting the environment keep track of some info, we can give simpler agents more complicated, and smarter-seeming, behavior. It's, more or less, offloading some processing to the environment itself so the agents within operate at a higher level. So it isn't just about pathfinding :3

Seregon wrote:
Those agents outside the players areas will be vastly simplified, and probably won't need any pathfinding at all (they will either not have a tracked position, or be allowed to ignore obstacles).
Very true -- which would mean a smaller diffusion map to track, which again I may have misrepresented, since it isn't all about pathfinding.

Edit:
It just occurred to me that we could parallelize the blending step using some OpenCL, which would cut down on the time costs a lot. For that of course, we'd need to add OpenCL as a dependency, but that would (almost definitely) pay dividends later. (Conveniently enough, I'm learning OpenCL at work right now :P)


Last edited by moopli on Sat May 24, 2014 4:11 pm; edited 1 time in total (Reason for editing : yay OpenCL)
Back to top Go down
View user profile
Sponsored content




PostSubject: Re: Pathfinding Antipatterns   Today at 11:48 pm

Back to top Go down
 
Pathfinding Antipatterns
View previous topic View next topic Back to top 
Page 1 of 1

Permissions in this forum:You cannot reply to topics in this forum
Thrive Game Development :: Development :: Programming :: Technical Discussion-
Jump to: