tag:blogger.com,1999:blog-12728036593215395982024-03-19T01:48:43.691-07:00Digesting DuckBlog about game AI and prototypingMikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.comBlogger163125tag:blogger.com,1999:blog-1272803659321539598.post-38108006663491729822012-05-31T11:17:00.001-07:002012-05-31T11:18:15.021-07:00Detour Crowd Path Replanning<iframe allowfullscreen="" frameborder="0" height="281" mozallowfullscreen="" src="http://player.vimeo.com/video/43175967" webkitallowfullscreen="" width="500"></iframe>
<br />
<br />
<br />
<br />
Path replanning for Detour Crowd has been a long time pet peeve of mine. I've blogged about the problems surrounding it earlier, but very little code has been submitted. I've been testing some ideas along the way, but never managed to have the few hours of solid coding to get all the pieces together.<br />
<br />
Here's what happens in the above video:<br />
<ul>
<li>At start all the agents find a short parts towards the goal. In the video they intentionally get stuck at local minima at start. Generally this improves responsiveness, but sometimes the agents move to wrong direction for a moment.</li>
</ul>
<ul>
<li>During movement the agents will replan their paths if they notice that the navmesh has changed in front of them. When the agents turn to purple, it means that they are replanning their paths. Similar small search is performend when the replanning occurs, but polygons along the existing path are favored. This makes changes close the agent responsive and changes further away does not make any visual change at all.</li>
</ul>
<ul>
<li>When the agent approaches the end of the path and the last polygon on the path is not the goal polygon, the agent will periodically replan the path. When a pathway to the goal opens, the agent will use that path.</li>
</ul>
On top of that there is the path topology optimization going on too. I think the recent changes made that pretty much irrelevant–I think it might be better to just fire a replan every now and then just for the kicks.<br />
<br />
I think that summarizes my thinking about path following in general. Once the world is constantly changing, the system ends up replanning the whole time. You cannot replan as much as you would like to since it is hard to determine how long A* will take, so the system becomes this weird scheduler-caching-magic-fudge-latency-hiding-box. There are these dynamic planning algos, like D*, but they all require too much memory.<br />
<br />
I hope to get to have the change to put another pass on Detour Crowd replanner to make it much simpler and more robust. Now there is too much state management spaghetti in there.<br />
<br />
The changes are available in SVN, please not that I removed the adjust move target function as it was complicating the logic too much. If you are using it, please let me know and I'll try to figure out similar functionality. I also added velocity control for agents (for player characters and such).Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com123tag:blogger.com,1999:blog-1272803659321539598.post-65296269338900408932012-05-29T23:15:00.000-07:002012-05-29T23:15:19.427-07:00Crafting 3D User Interfaces for the Web<script async="" class="speakerdeck-embed" data-id="4fbfcc126ab039001f027280" data-ratio="1.7777777777777777" src="//speakerdeck.com/assets/embed.js">
</script>
<br />
I had a talk a little while ago at local frontend dev event called Webshaped. My talk was about how to craft easy to use, tangible 3D UIs. This is one of the dearest topics to me, and I think I overdid the presentation a bit. It kinda became a mash-up between a game design talk and UI talk for kinda designers and sorta programmers (or developers as web folks like to call them).<br />
<br />
I think I will redo the presentation at some point in the future if such an opportunity presents itself. Maybe more focused on some of the sub topics, or more maybe with interactive things to try out etc.<br />
<br />
I have not talked much about Tinkercad on my blog so far. A lot of the interesting stuff about Tinkercad does not quite fit the voice of this blog, but I think I'll write a thing or two about it.<br />
<br />
For those who don't know, Tinkercad is super easy to use 3D modeling tool for makers, artist and tinkerers alike. It works directly in your browser. Under the hood Tinkercad is a solid modeler, which means that all the stuff you make with Tinkercad can be 3D printed.<br />
<br />
Here's something we did just recently, an embeddable viewer for your projects. The project shown below is a plan of our deck with summer furniture and some gardening stuff.<br />
<br />
<br />
<iframe frameborder="0" height="350" marginheight="0" marginwidth="0" scrolling="no" src="https://tinkercad.com/embed/8NG4sgAkpgN" width="560"></iframe>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com18tag:blogger.com,1999:blog-1272803659321539598.post-86183203612565312692012-05-20T02:21:00.002-07:002012-05-20T02:21:36.338-07:00Loose Navigation Grid Prototyping<iframe allowfullscreen="" frameborder="0" height="281" mozallowfullscreen="" src="http://player.vimeo.com/video/42485281" webkitallowfullscreen="" width="500"></iframe>
<br />
<div class="first" style="background-color: #f4f5f7; padding: 0px;">
</div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><br /></span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;">I had a little time this weekend to work on AI again. I've blogged earlier about loose navigation grids, and now I finally got it to the point that it starts to look interesting. Above is a video showing the current prototype in action.</span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><br /></span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><b>Path Planning in Dynamic Worlds</b></span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><br /></span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;">In addition to this example, I've been working on path replanning in DetourCrowd. It has become painfully obvious, that the most limiting factor for pathfinding is that we assume that it is perfect. Dynamic worlds make this pain a migraine.</span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><br /></span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;">If the world is constantly changing, the notion of "path to the goal" becomes really hard to define. Even the goal itself becomes uncertain. For example if we picked a cover point and the level around the AI and the cover changed, is the cover a good choice any more? The more I've thought about it, the broader the problem has spread.</span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><br /></span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;">I have earlier discussed that I think in changing worlds, the contract between the behavior and the pathfinder should be the initial path. If the initial path changes too much, then the behavior plan fails and the behavior should replan too. This does not seem to be well accepted idea, so I've started to rethink the problem.</span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><br /></span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;">The feedback I'm getting from the people who are using Recast is that they would just like everything to work. Out of the box, don't-tell-me-how-it-works.</span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><br /></span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><b>Loosing Up the Constraints</b></span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><br /></span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;">So the idea I'm toying with the loose navigation grids is that you just drop your character in the world, tell it to go to some location and it happens or not. The important idea I'm testing here is that can we make the navigation system uncertain? There is no guarantee that the agent will find its' way to the goal, but it will try, with limited horizon of information.</span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><br /></span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;">This allows a couple of things. Firstly, since we know that we have limited view of the world, we can use greedy search algorithm and replan to our hearts content. We're side stepping A* worst case performance which means visiting all the nodes in the graph. Secondly, accepting the limited information again, interesting culinary opportunities open up as such as exploring the navigable space more locally, iteratively, patching things up as we go, throw away information that is too far.</span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><br /></span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;">The down side is that given the local nature of the search space, the system will get stuck in local minima. But then again, how big are local minimas in games? MMOs may have the nasties pathfinding problems of the all, but I think they should use hierarchies to hide the complexity. </span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><br /></span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;">I think this has been interesting though process so far. I've been able to let loose a lot of preconceptions and limitations I had before.</span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><br /></span></span><br />
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><b>The Prototype</b></span></span><br />
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><br /></span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;">In the above video you'll sees that the loose navigation grid is build on the fly by starting at a seed point (i.e. character location). The exploration step looks at open edges in the local nav grids (hilighted at the end of the video) and creates a new grid at such location. Path planning is done hierarchically, first between the grids and then within one small local 2D grid.</span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><br /></span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;">The navigation structure should be "self healing". If an obstruction is added or removed, the intersecting grids can be deleted and exploration phase can be rerun on the neighbors of the deleted nodes to fill in the space.</span></span><br />
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><br /></span></span><br />
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;">Next time I'll have a little time I will try to make the whole path finding and movement to work to see how good it looks and then it is time to test some destruction.</span></span></div>
<div class="first" style="padding: 0px;">
<span style="color: #71767a; font-family: helvetica, arial, sans-serif;"><span style="line-height: 21px;"><br /></span></span></div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com15tag:blogger.com,1999:blog-1272803659321539598.post-73941506032014487652012-04-24T23:16:00.004-07:002012-04-24T23:16:49.237-07:00Ludum Dare 23<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiUNzsWERgyU6qGw8ObIFwn0Spp10TeFnvF2P-sITCjFEXwm2QwaESBJWgLHX9wkmfktlXzadcKMQ0bZIJm5GlghWTkYKxoTkKk43Ct3OAt9VyD-cu_POrdPKmsObHTXdlchyphenhyphenD8uaEge54d/s1600/Screen+shot+2012-04-25+at+8.34.14+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="311" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiUNzsWERgyU6qGw8ObIFwn0Spp10TeFnvF2P-sITCjFEXwm2QwaESBJWgLHX9wkmfktlXzadcKMQ0bZIJm5GlghWTkYKxoTkKk43Ct3OAt9VyD-cu_POrdPKmsObHTXdlchyphenhyphenD8uaEge54d/s400/Screen+shot+2012-04-25+at+8.34.14+AM.png" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<i><br /></i></div>
<div class="separator" style="clear: both; text-align: left;">
Last weekend I took part in <a href="http://www.ludumdare.com/">Ludum Dare</a> game development compo. I've been jealous to <a href="http://jet.ro/">Jetro</a> for a long time because he always manages to make something great in these compos. So I took the time and bit the bullet myself.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
The game I made for the compo is called <a href="http://www.ludumdare.com/compo/ludum-dare-23/?action=preview&uid=12280">Gingerbread Kingdom</a>, it is kind of a mix between Carcassonne, Tower Defence and Rampart.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjni_JvqGI2Hh-uOAaBTNZ-ogBWrmEL_Hw2QzidRA_lruHFM-6ys0XxCZzB0c5DiyuNfutELWheyI9KvHz7PtsQQ6HSwSP2um5QXFmDmZojWWnNMTsE2KuSZ30e-BuhOypGwhUUqIc8mzoH/s1600/ludum-dare.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="157" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjni_JvqGI2Hh-uOAaBTNZ-ogBWrmEL_Hw2QzidRA_lruHFM-6ys0XxCZzB0c5DiyuNfutELWheyI9KvHz7PtsQQ6HSwSP2um5QXFmDmZojWWnNMTsE2KuSZ30e-BuhOypGwhUUqIc8mzoH/s400/ludum-dare.jpg" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both;">
<i><br /></i></div>
<br />
<div class="separator" style="clear: both; text-align: left;">
I set a couple of constraints to myself before I started: 1) Simple, 2) 2D Game, 3) written in Javascript. I often manage my daily work using disposable prioritized todo lists (<a href="http://zenhabits.net/">Babauta</a> style), and I often doodle pictures to set myself longer term goals. The castle and the giant in the above picture is the one that kept me going in the Ludum Dare concept (even if giants turned into birds later on). I had the idea of using the Carcassonne tiles from get go. When I saw the last theme voting, it was quite clear that it would fit in any of the ideas.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
Equipped with these ideas I started to work on placing the tiles, finding complete castles and scrolling the area. Initially I had the idea that the world would be infinite (of course!), as I went on I kept on making it smaller and smaller, until at very end I removed vertical scrolling. On hindsight, I think the game would be twice as fun if it did not have any scrolling at all.<br />
<br />
One tile placement was working and I could detect the castles, it was time for some enemies. At this point the world was still infinite and I struggled to figure out a way to spawn enemies from any direction without making the game too frustrating. In the spirit of getting things done, I just made them always spawn from right, and afte I had implemented the first version, I did not see any reason to make it more elaborate.<br />
<br />
Once I got the basic conflict set up, the hardest part of the project started: balancing. This was around the evening of the first day, and I was getting a bit worn out already. And boy was it hard! The game was not fun, it was unbalanced, unfair, buggy and I just had to keep on going to play it.<br />
<br />
To get past that stage, I kept writing tiny lists of things that needs fixing, and fixed them and moved on. After some passes I started to see a game emerging, and it was time to start pruning things. The biggest change for me was to shrink the playfield. When I got the idea to use the Carcassonne tiles, I wanted to solve the Carcassonne problem that you run out of table. It took me more time than necessary to let go of that idea.<br />
<br />
It has historically been really hard for me to design game endings. I can kinda make ok-ish failure conditions, but defining the point where you have won a game is just somehow out of my character. For example my earlier game Zen Bondage did not have game ending at all, you just had to decide that you're done. I kinda got away with it with the Buddhist theme there :)<br />
<br />
So when I finished my "all nighter" around 2 am the first day, I had my basic game done.<br />
<br />
The next day I concentrated on making game ending, and making the game more understandable. My design philosophy is: use less energy to decode more information. Usually this require rounds of user testing, and reworking things. This phase usually includes adding some kind of indication to all meaningful state transitions in the game.<br />
<br />
My favorite tools for these indicators are particle systems and procedural animations. I think the 1.5 hours I spent on making that procedurally animated bird was well worth it. I wish I had had another 1.5 hours to spend on making a simple particle system, which I could have sprinkled all over the place.<br />
<br />
I left the winning condition to very last stage of the project. I generally hate boss battles, so that was yet another mental struggle to get through. I'm glad my fiancee insisted on having a boss fight in the end :) Once I had it implemented, I had a stream of other ideas how to make the overal progress better, but no time.<br />
<br />
<br />
The ideas that spawned the day after when I saw people actually play the game were:<br />
<br />
<ul>
<li>make tile rotation instructions in bigger, bolder, blinkier and fancier text </li>
<li>no scrolling, make the gamefield fit on screen</li>
<li>add level of increasing difficulty</li>
<ul>
<li>could be procedurally generated</li>
</ul>
<li>ramp up difficulty based on enemies and terrain (water tiles)</li>
<li>better indication which tiles are ready to fire</li>
<li>lasers!</li>
</ul>
<br />
<br />
All in all I think it was a great project. the biggest lessons were that it is really hard to balance a game system when you're really tired. It turned out to be equally nasty to find bugs in dynamic language, especially refactoring was something was huuge pain. Next time I'll set up closure compiler from the start. I'm most proud that I was able to keep it simple and finish the game.Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com11tag:blogger.com,1999:blog-1272803659321539598.post-82881074766284307912012-04-15T06:07:00.002-07:002012-04-15T06:12:02.751-07:00Demopaja Sources<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgBpVZSiHij9wCvU5OkOWDM868F17wJetyX9hyMW925l2vO6kYbgwSxGTeT-hW_nlIIVt-NdfFTcHcC909Pb7D2mm70jdp30vj1oiJ0rnzBBDtYZ1I87WuTz2i6asiG0DmpYJFyQCk9MozR/s1600/demopaja.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="296" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgBpVZSiHij9wCvU5OkOWDM868F17wJetyX9hyMW925l2vO6kYbgwSxGTeT-hW_nlIIVt-NdfFTcHcC909Pb7D2mm70jdp30vj1oiJ0rnzBBDtYZ1I87WuTz2i6asiG0DmpYJFyQCk9MozR/s320/demopaja.jpg" width="320" /></a></div>
<br />
Inspired by Farbrasuch's release of their demo tools, I decided to dig up my old Demopaja backup, clean up some directories from random crap, and put it up here for downloads:<br />
<ul>
<li><a href="https://sites.google.com/site/recastnavigation/Demopaja_050508.zip">Demopaja_050508.zip</a></li>
</ul>
<div>
I don't have Windows dev machine these days anymore so I have no idea if it still compiles. I think it compiled back in 5th May in 2008 when I looked at it the last time.</div>
<div>
<br /></div>
<div>
I'm still quite proud of the tool, the documentation and all that. Even if I do despise the coding style – I was young then, you know.<br />
<br />
<span style="font-size: x-small;"><b>[EDIT]</b></span> You can treat the code public domain, some libs and snippets have their own licenses, treat them appropriately.</div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com64tag:blogger.com,1999:blog-1272803659321539598.post-24856002305343517572012-02-26T23:18:00.002-08:002012-02-26T23:19:07.335-08:00Choosing random location on navmesh<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiNuFuKRGSf1-WWLWt3-w_6LCcg06Lir0wzHDn2xv30BpG-f2fAHXeqxhBIkX0d4-wA5jH4hcLSZyf1t08rBVnHaUqK52pNT2iRbEuxQ72xtEzvEaErp3Net3O1Zfzq7-mUA6iezPHzRFip/s1600/Screen+Shot+2012-02-27+at+8.42.01.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="232" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiNuFuKRGSf1-WWLWt3-w_6LCcg06Lir0wzHDn2xv30BpG-f2fAHXeqxhBIkX0d4-wA5jH4hcLSZyf1t08rBVnHaUqK52pNT2iRbEuxQ72xtEzvEaErp3Net3O1Zfzq7-mUA6iezPHzRFip/s320/Screen+Shot+2012-02-27+at+8.42.01.png" width="320" /></a></div>
<br />
I added two methods to generate random points on navmesh to Detour. The first method generates random points anywhere in the mesh based on query filter, and the second method generates random points around a specified location. The first one is good for choosing just some random location, and the second one is good for finding a location which is guaranteed to be connected to the start location.<br />
<br />
<div class="p1">
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span"> </span><span class="s1"><span style="color: #45818e;">dtStatus</span></span> findRandomPoint(<span class="s2">const</span> <span class="s1"><span style="color: #45818e;">dtQueryFilter</span></span>* filter, <span class="s2"><span style="color: #a64d79;">float</span></span> (*frand)(), <span class="s1"><span style="color: #45818e;">dtPolyRef</span></span>* randomRef, <span class="s2"><span style="color: #a64d79;">float</span></span>* randomPt) <span class="s2"><span style="color: #a64d79;">const</span></span>;</span></div>
<div class="p1">
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span></div>
<div class="p1">
</div>
<div class="p1">
<span style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span"> </span><span class="s1"><span style="color: #45818e;">dtStatus</span></span> findRandomPointAroundCircle(<span class="s1"><span style="color: #45818e;">dtPolyRef</span></span> startRef, <span style="color: #a64d79;"><span class="s2">const</span> <span class="s2">float</span></span>* centerPos, <span style="color: #a64d79;"><span class="s2">const</span> </span><span class="s2"><span style="color: #a64d79;">float</span> </span>maxRadius, <span class="s2"><span style="color: #a64d79;">const</span></span> <span class="s1"><span style="color: #45818e;">dtQueryFilter</span></span>* filter, <span class="s2"><span style="color: #a64d79;">float</span></span> (*frand)(), <span class="s1"><span style="color: #45818e;">dtPolyRef</span></span>* randomRef, <span class="s2"><span style="color: #a64d79;">float</span></span>* randomPt) <span class="s2"><span style="color: #a64d79;">const</span></span>;</span></div>
<div class="p1">
<br /></div>
There were two tricky parts on choosing a good random location. The first was how to make sure that the random samples are more or less uniform, that is, the area of a polygon needs to be considered. Secondly, the filters and off-mesh connections make picking random polygon quite hard.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh5LDCfiKHUB_caiT1Ml_MN38dmf6589rukwsajNCBDlbxpuczlCHyt6ugTsfi0FXvZaBD2Av8Mvrof4IkGnqLM2w2TsvfGOOqD9McT3xwB10k1u-fsZpTzLQeXYc7XdfnVcS4ENNNYS9uP/s1600/Screen+Shot+2012-02-27+at+8.43.42.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="210" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh5LDCfiKHUB_caiT1Ml_MN38dmf6589rukwsajNCBDlbxpuczlCHyt6ugTsfi0FXvZaBD2Av8Mvrof4IkGnqLM2w2TsvfGOOqD9McT3xwB10k1u-fsZpTzLQeXYc7XdfnVcS4ENNNYS9uP/s320/Screen+Shot+2012-02-27+at+8.43.42.png" width="320" /></a></div>
<br />
In general the filtering can be used to prevent generating random points in disabled areas, but you can also mark certain areas (i.e. spawn locations) and restrict the point generation only to those locations using filter flags.<br />
<br />
I wanted to avoid allocations, so I started to look for a "streaming" random selection algorithm. The solution turned out to be <a href="http://en.wikipedia.org/wiki/Reservoir_sampling">Reservoir Sampling</a>. I modified it a bit to make it consider the area of a polygon.<br />
<br />
Area weighted reservoir sampling looks something like this:<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">poly = nil</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">areaSum = 0.0</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">foreach p in polygons {</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> area = p.area()</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> areaSum += area</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> if (frand()*areaSum <= area) {</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> poly = p</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">}</span><br />
<br />
Where frand() returns a random number in range [0..1). The basic idea is that each polygon is chosen at decreasing probability relative to the polygon area.<br />
<br />
The good thing is that this algorithm works great in practice, the bad thing is that it is a bit slow. It needs to visit all polygons and calculate their area. This could be sped up by caching the calculations, but different filter types make this quite cumbersome in practice.<br />
<br />
The code was committed in R331.Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com12tag:blogger.com,1999:blog-1272803659321539598.post-74578933461101908862012-01-01T07:54:00.000-08:002012-01-01T07:54:32.732-08:00Loose Navigation Grids<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-gIs3fG2xzwo/TwCAqeJtAFI/AAAAAAAAAXU/mTPn5HNPmFU/s1600/loose_1.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="210" src="http://3.bp.blogspot.com/-gIs3fG2xzwo/TwCAqeJtAFI/AAAAAAAAAXU/mTPn5HNPmFU/s400/loose_1.jpg" width="400" /></a></div>
<br />
<br />
Due to my startup, I have not had much time to do navigation research last year. I think I have been thinking on my few odd spare cycles is the idea of loosely connected grids, which kind of mixes waypoints and grids for the ultimate dynamic navigation. I had a little time during holidays and I thought I'd give it a spin.<br />
<br />
<b>A Grid</b><br />
<br />
The whole process starts with voxelizing the level geometry much like in Recast and finding walkable surfaces. After that the area is converted to a 2D heighfield. This is done by doing a breath-first search starting from the center of the walkable surface. The voxelization is created around a point on walkable space, so this location is guaranteed to be walkable. This initial step finds contiguous walkable area that can be stored in 2D grid.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-k0arJjjYn9k/TwCAyQnf_MI/AAAAAAAAAXg/nRato3Q9lR4/s1600/loose_2.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><br class="Apple-interchange-newline" /><img border="0" height="255" src="http://4.bp.blogspot.com/-k0arJjjYn9k/TwCAyQnf_MI/AAAAAAAAAXg/nRato3Q9lR4/s320/loose_2.jpg" width="320" /></a></div>
<div>
<br /></div>
<br />
The property I tried to improve in the voxelization phase compared to Recast is the bounds. In Recast each tile requires to voxelize a column which cuts through the whole world vertically. This makes the runtime for the voxelization really unpredictable. In this version the grid voxelization bounds are always the same, which makes the whole process more predictable in terms of max memory and processing.<br />
<br />
<b>Automatic Exploration</b><br />
<br />
As you can see from the image, the voxelization bounds are a bit larger than the actual grid. The larger area is used for two purposes. Firstly, it allows to counter for the obstacle expansion like in Recast, and secondly, it allows to calculate which neighbor cells in the 2D grid will lead to unexplored space. The dark outlines in the grid shows cells whose neighbor cells lead to unexplored space, I call these border cells.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-xLLCYyNFhhg/TwCA6yxbG_I/AAAAAAAAAXs/u-mbTqNX7NI/s1600/loose_3.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><br class="Apple-interchange-newline" /><img border="0" height="162" src="http://4.bp.blogspot.com/-xLLCYyNFhhg/TwCA6yxbG_I/AAAAAAAAAXs/u-mbTqNX7NI/s400/loose_3.jpg" width="400" /></a></div>
<div>
<br /></div>
<br />
These border cells are used to find few good locations for new grids. The process for find new grid locations starts by sorting all the border cells so that the nearest cell to the center is first. Each of these seed cells are visited in turn and if the location is not occupied yet, a new grid location is stored, and a perimeter around the grid location is marked as occupied. I use breath-first flood fill for this. A perimeter up gridSize/2 distance is marked as occupied. The yellow ticks in the above image mark these locations.<br />
<br />
In addition to the flood fill, overlap of neighbor grids is used to filter new grid location generation.<br />
<br />
The whole exploration process starts from one grid and it's potential new grid locations expanding until the whole connected walkable surface is covered. That is, because the neighbor overlap is taken into account, the process will some point just terminate, since there are no more new potential grid locations.<br />
<br />
Finally connections between the grids are found. For each grid overlapping grids are found (the check is done at cell level), and closest 6 grids are stored as neighbors.<br />
<br />
<br />
<b>Path Planning</b><br />
<br />
I have not yet implemented this phase, but this is how I think it should be done.<br />
<br />
In order to move an agent in the world, first an A* search is done along the high-level graph which connects the grids. This path can be continuously replanned to take into account changes in the graph.<br />
<br />
Movement within one grid is calculated using <a href="http://digestingduck.blogspot.com/2010/03/local-navigation-grids.html">simple grid path planner</a>. In order to move the agent from the current grid to the next grid, the goal is set to the nearest point which in the next grid. This should create similar behavior as described in <a href="http://www.youtube.com/watch?feature=player_embedded&v=7qfJ8w6JXco">Way Portals</a>. It is quick to calculate the overlap between two grids, so it can be calculated on the fly. Once the agent is on the next grid, the next grid is set as current grid, and overlap is calculated and movement towards the next grid begins.<br />
<br />
<br />
<b>Future Improvements</b><br />
<br />
There's a lot of work to be done to improve grid placement during the exploration phase. Currently there is too much of overlap, and this could be improved by voxelizing a bit larger area and using that extra area beyond the grid size to find the new grid locations. This extra padding could be also used to sample jump-links as per my <a href="http://digestingduck.blogspot.com/2011/07/paris-gameai-conference-2011-slides-and.html">Paris 2011 persentation</a>.<br />
<br />
<br />
<b>Conclusion</b><br />
<br />
Building efficient navigation structure for dynamic worlds is tricky. I think this technique has a lot of potential. For a long time I thought that grids are too memory heavy, but the real break through for me was when I realized that the grids can be kept compressed in the memory. This reduces the memory consumption down to the same level as navmeshes.<br />
<br />
The technique combines small grids with waypoint graph. I think it has a lot of "roadmap" flavor to it. Here's some important properties of this navigation method:<br />
<br />
<ul>
<li><b>Local</b>: Pretty much every aspect of the technique is local: generation of each grid is local, traversing of each grid is local, updates to the grid are local too. This is important to keep the memory and processing in budget.</li>
<li><b>Hierarchical</b>: In order to make path replanning fast, the navigation representation needs to be hierarchical. Replanning should do only small amount of work, and the rest of the system should iteratively find more precise solution.</li>
<li><b>Dynamic</b>: When something changes in the game world, it needs to be reflected in the navigation graph too. Firstly, this technique allows quick updates to the navigation representation. Building individual pieces as well as connecting them together needs to be flexible and fast.</li>
</ul>
<br />
I think this is the way to implement path planning in 2012!<br />
<br />
<br />
Download prototype and code (OS X):<br />
<br />
<ul>
<li><a href="https://sites.google.com/site/recastnavigation/navtest.zip">navtest.zip</a></li>
</ul>
<br />
<br />Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com23tag:blogger.com,1999:blog-1272803659321539598.post-32189618962760442322011-10-23T04:24:00.000-07:002011-10-23T04:38:53.781-07:00Path Replanning<br />
I've been picking on path replanning again. It is interestingly annoying problem. I have currently settled on following idea to make it somewhat manageable.<br />
<br />
<b>Prerequisite</b><br />
In ever dynamic game world, the path finding and path following becomes statistic. The changes are that most of the time your request does not pan out the way they were requested. It is really important to have good failure recovery, both on movement system level as well as on behavior level. Plan for the worst, hope for the best.<br />
<br />
<b>Movement Request</b><br />
At the core of the problem is movement request. Movement request tells the crowd/movement system that a higher level logic would like an agent to move to a specific location. This call happens asynchronously.<br />
<br />
<b>Path to Target</b><br />
When the request is processed, the movement system will find the best path to the goal location. If something is blocking the path, partial path will be used and the caller is signaled about the result. From this point on, the system will do it's best to move the agent along this route to the best location that was just found.<br />
<br />
<b>Path Following</b><br />
If a disturbance is found during the following, the movement system will do a small local search (same as the topology optimization) in order to fix the disturbance. If the disturbance cannot be solved, the system will signal that path is blocked and continue to move the agent up until to the valid location on the current path unless it is interrupted.<br />
<br />
<b>API</b><br />
This could lead to following interface between the high level logic and the movement request.<br />
<br />
<code></code><br />
<pre><code>struct MovementRequestCallback
{
<span class="Apple-style-span" style="color: #6aa84f;"> // Called after path query is processed.
// (Path result accessible via ag->corridor)
// Return true if path result is accepted.
</span> virtual bool result(Agent* ag) = 0;
<span class="Apple-style-span" style="color: #6aa84f;"> // Called when path is blocked and
// cannot be fixed.
// Return true if movement should be continued.
</span> virtual bool blocked(Agent* ag) = 0;
<span class="Apple-style-span" style="color: #6aa84f;"> // Called when the agent has reached
// the end of the path trigger area.
// Return true if movement should be continued.
</span> virtual bool done(Agent* ag) = 0;
};
bool dtCrowd::requestMovement(int agent,
const float* pos, const dtPolyRef ref,
MovementRequestCallback* cb);</code></pre>
<div>
<br /></div>
The 'result' callback allows the high level behavior to cancel movement in case unfavorable path rest is found (i.e. partial path), or it allows the behavior to set some internal state based on the path result.<br />
<br />
The 'blocked' function allows the higher level logic to handle more costly replans. For example the higher level logic can try to move to a location 3 times until it gives up and tries something else, and it can even react to replays if necessary.<br />
<br />
The 'done' function allows to inject extra logic on what to do when path is finished. For example a 'follow enemy' behavior may want to keep on following the goal even if it is reached, whilst 'move to cover' might do a state transition to some other behavior when the movement is done.<br />
<br />
The general idea is to move as much of the state handling behavior out from the general code, and try to make the replan to be as cheap as possible. The downside is that the replan cannot react to big changes in the game world, but I argue that that is not necessary and should be handled with higher level logic anyway (i.e. the path can be come much longer).<br />
<br />
What do you think?<br />
<div>
<br /></div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com9tag:blogger.com,1999:blog-1272803659321539598.post-88825697903908217142011-08-01T08:03:00.000-07:002011-08-01T08:21:56.542-07:00Hierarchical Pathfinding in Detour<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhjJ9VbdW6xlj-Zm2CKe8Xy5XGIBb4XyyhJP0KGVSsfs-TGMkxYwvv1b_rBf-VcR75bxZE1qXcIw__qvBXn74HUSmaubcI0x6lBXg7s4nn-yZIp52LGwez6IBPJgtQLx3Tgbn2iPy2w9p3h/s1600/Screen+shot+2011-08-01+at+6.17.19+PM.png" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 229px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhjJ9VbdW6xlj-Zm2CKe8Xy5XGIBb4XyyhJP0KGVSsfs-TGMkxYwvv1b_rBf-VcR75bxZE1qXcIw__qvBXn74HUSmaubcI0x6lBXg7s4nn-yZIp52LGwez6IBPJgtQLx3Tgbn2iPy2w9p3h/s400/Screen+shot+2011-08-01+at+6.17.19+PM.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5635907693543914914" /></a>Uwe Koch has written a great thesis about hierarchical pathfinding with navmeshes. He presents a generalized version of HPA* implemented in Detour. The short summary: 4-5 times faster than Detour's A*, and uses 10-20 times less memory (graph nodes).<br /><br /><div><div><b>Applying graph partitioning to hierarchical pathfinding in computer games</b></div><div><ul><li><a href="http://soclose.de/misc/thesis/thesis_ghpaStar.pdf">Thesis</a></li><li><a href="http://soclose.de/misc/thesis/thesis_code.zip">Source code</a></li></ul></div></div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com24tag:blogger.com,1999:blog-1272803659321539598.post-50444343545837016032011-08-01T03:53:00.000-07:002011-08-01T04:57:12.843-07:00Path Replanning in DetourCrowd<div style="text-align: center;"><iframe src="http://player.vimeo.com/video/27143809?title=0&byline=0&portrait=0" width="400" height="225" frameborder="0"></iframe></div><div>
<br /></div><div>I just added first version of path replanning for DetourCrowd. If a polygon becomes invalid along the path, the path is replanned. Invalid polygon means that the polygon just disapperas (i.e. a tile is removed), or its' flags don't match with the filter anymore. In the above video, the red polygons have disabled flags and the agents react to the changes over time.</div><div>
<br /></div><div>The way it works on practice is that before the current path is followed, we peek ahead to make sure the next N polygons are valid (I used 10 in the above example). If a any polygon during that sub path is invalid, a replan is issued from the furthest valid position along the path. if the current polygon becomes invalid, or of the target location becomes invalid, the agent will stop.</div><div>
<br /></div><div>There are some things I don't like about this method. Firstly, it is quite wasteful in resources. Issues almost a full replan is pretty horrible. I tried some local repair operations, but they ended up being too very complicate and hard to time-slice.</div><div>
<br /></div><div>Secondly, the replanning does not react if a new venue becomes available. The topology optimization pass will catch many of these cases, but if the goal was unaccessible when the replannig happened, the current implementation will not try to replan when it reaches the end of the path.</div><div>
<br /></div><div>The end of the path could be flagged or some other tricks, but I think I might be missing a bit bigger picture here. What actually does a movement request mean?</div><div>
<br /></div><div><meta charset="utf-8"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiwRvbtoPdyRqryiS0F2V1oMymq3Vmxi5_eMv6UHB_qiQh7eNaZGhmdifzuea8nNUUr6BCfwOaFTH0z2J3TzXP9nlwJIlpAJ5Mlry7QnaDP9nfvhG4_Vs56QGLNQij7xOpTUBY4QUVRqRUc/s1600/path_example.jpg" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiwRvbtoPdyRqryiS0F2V1oMymq3Vmxi5_eMv6UHB_qiQh7eNaZGhmdifzuea8nNUUr6BCfwOaFTH0z2J3TzXP9nlwJIlpAJ5Mlry7QnaDP9nfvhG4_Vs56QGLNQij7xOpTUBY4QUVRqRUc/s400/path_example.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5635848185840490674" style="display: block; margin-top: 0px; margin-right: auto; margin-bottom: 10px; margin-left: auto; text-align: center; cursor: pointer; width: 400px; height: 329px; " /></a></div><div><b>Example of nasty case</b></div><div>
<br /></div><div>Here's a simple example which emphasizes one of the problems with replanning. There is a house and it has a door which can be open or closed. The NPC does not have key (cannot open door), and wants to move inside the house. If the door is open, the NPC can walk in, that is path A in the picture. But what should be do if the door is closed?</div><div>
<br /></div><div>From navmesh point of view, it looks like the graph is broken at the location of the door. The usual fall back in case no path is found is to return a path which leads to nearest position around the target. In our case that would be the path B in the picture.</div><div>
<br /></div><div>It is really hard to tell the A* that there actually is a closed door and that the nearest accessibility to goal location is semantically the door. And this is when things start to slip from a technical issue to a simulation or story issue.</div><div>
<br /></div><div>Imagine a case where the agent starts to move to the building, and before it gets there the door is closed. The story seen by the player could be something like this: The bad guard tried to capture the princess, but at the last moment the princess managed to close the door, and then the guard went to hide under the trees.</div><div>
<br /></div><div>Game levels are full of cases like this. The AI has no notion of the trees, but when the AI walks under a tree and stands there, the player will give meaning to it.</div><div>
<br /></div><div>There are more problems with that case too. For a moment imagine that we could replan the path every time the world changed. Now if we had a situation where the door would open and close every few seconds, the agent would get dead locked at the east side of the building since the solution would flicker between paths A and B.</div><div>
<br /></div><div>These are just few examples which happen when you add replanning to your navigation system.</div><div>
<br /></div><div><b>Solution</b></div><div>
<br /></div><div>I think the proper solution to reacting to dynamic changes in the navigable surface is to treat the planned path the same way as any other plan in the AI system. That is, it is very likely to fail, and the plan will be considered as failed, if small adjustments to it cannot fix it. This makes assumptions about the request quite clear. It may not be the best solution, but I think it puts the decision at the right spot.</div><div>
<br /></div><div>
<br /></div><div>Request for comments! How do you handle partial paths and replanning?</div><div>
<br /></div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com13tag:blogger.com,1999:blog-1272803659321539598.post-34528548524970963392011-07-03T03:36:00.000-07:002011-07-03T10:33:32.829-07:00Paris Game/AI Conference 2011 Slides and Demo<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhIrK9s905pm2RPYLFwpxdunZ4nMuczhfdVcUaNRiavfStrsvw1WkMtxVZGliuOhlon5vdjd0AGFsU9nqKJ6JveO5kiI10100NbWMe0sq3nrpdGe6SIFo2mZu0sK2yuQCIeZa8HscLfqNci/s1600/Screen+shot+2011-07-03+at+1.38.25+PM.png" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 289px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhIrK9s905pm2RPYLFwpxdunZ4nMuczhfdVcUaNRiavfStrsvw1WkMtxVZGliuOhlon5vdjd0AGFsU9nqKJ6JveO5kiI10100NbWMe0sq3nrpdGe6SIFo2mZu0sK2yuQCIeZa8HscLfqNci/s400/Screen+shot+2011-07-03+at+1.38.25+PM.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5625073708586268162" /></a><div>The Paris Game/AI Conference is over and it was a blast! There was just so much interesting stuff in there that my head was just about to burst. I really like the shooter symposium where handful of studios gave microtalks (about 15mins each) on similar subjects followed by a panel discussion and Q&A. It was really inspiring to see different ways to solve similar problems.</div><div><br /></div><div><br /></div><div>My talk this year was about some work I did for Killzone3. I made a handful of tools for them to improve their AI level design workflow. In my talk I concentrated on how to automatically build cover annotation for the player. Killzone has this mechanic where the player can latch to a cover and slide along it. AI cover locations are discrete points are explained and were deducted from the player cover.</div><div><br /></div><div>The cover locations are found using voxelization and tracing the contours of voxelized areas. Then the contours are sampled to see if they are close to a wall, and further the wall height is calculated and cover planes are build from that.</div><div><br /></div><div>I also explained how this idea can be further expanded to automatically find jump-links and other non-locomotion navigation annotation.</div><div><br /></div><div>Here's the link to the slides and demo (with source, sorry only OSX binaries):</div><div><ul><li><a href="https://sites.google.com/site/recastnavigation/AIGD11_MikkoMononen_AutoAnnotations.zip">AIGD11_MikkoMononen_AutoAnnotations.zip</a></li></ul></div><div><br /></div><div><br /></div><div>I think the presentation did not go as well as last year. I tried to fix some problems I had last year, but ended up failing in some things I think nailed last year.</div><div><br /></div><div>Firstly, last year I had two topics, and it seems I was only able to get the second topic through. So my idea for this year was to present one battle-proven practical idea and show how to vary it. Hopefully with enough details that people can implement it and maybe fond other uses for the technique too. I think the scope was good this year.</div><div><br /></div><div>Secondly, even if I think my presentation last year was cool (and I got a lot of good feedback from it), I think it was a distraction. So this year I tried to simplify my slides to bare bones. The regular slides format does not work very well the way I like to explain things. I find it much easier to show different debug renderings in a demo and talk on top of that.</div><div><br /></div><div>I horrible mistake I made this year was that I did not have enough time to practice the presentation out loud, in front of other people. I chopped some topics, since my practice runs were always over time. During the presentation I was super nervous because I did not have good confidence on time, and I ended up rushing through the slides super fast.</div><div><br /></div><div>Lessons learned, I hope my next presentation will be much better :)</div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com21tag:blogger.com,1999:blog-1272803659321539598.post-49360078249492087422011-04-16T01:01:00.000-07:002011-04-16T01:20:34.574-07:00Temporary Obstacle Progress<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjxz3uMJ2X9ZioxvZavUrlAXUqOxfK-Vdebx6ZsjuUwTuvMYSEGus4yCMmRTxXyiqUHaN9j2isOVeODl8q0CcBuV7Zjyu7oWGinCibOC3kFazCrM7TYquimUqV-jvfBbjt3vvrEqcqF2qG4/s1600/temp_obstacles_progress.jpg" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 223px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjxz3uMJ2X9ZioxvZavUrlAXUqOxfK-Vdebx6ZsjuUwTuvMYSEGus4yCMmRTxXyiqUHaN9j2isOVeODl8q0CcBuV7Zjyu7oWGinCibOC3kFazCrM7TYquimUqV-jvfBbjt3vvrEqcqF2qG4/s400/temp_obstacles_progress.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5596088556906507826" /></a>I've been super busy recently. Our <a href="http://tinkercad.com">startup</a> just opened a public beta. I have managed to get some progress done on the temporary obstacle handling, though.<div><br /></div><div>This is now probably the 4th rewrite of the system, so things are slowly being massaged in place (it usually takes 5 rewrites :). Adding and removing obstacles works again, and I've done some good progress on making the tile cache class better. Though, the API is still a bit in flux.</div><div><br /></div><div>I'm currently testing with cylindrical obstacles, my plan is to support only extruded convex poly obstacles at first and add support for custom obstacles types in the long run.</div><div><br /></div><div>I get quite consistent average of 0.1ms per layer build time, and about 10% compression ratio of the layer data when using 48x48 layers. The compressed layer grid data needed to rebuild any navmesh tile with obstacles in the scene pictured above takes 75 kB. The navmesh itself for that scene takes 72 kB.</div><div><br /></div><div>I have few things left to do to finish this feature: 1) a custom pass before the mesh is being passed to navmesh builder (to handle flags), 2) handle off-mesh connections. Once that is done, I will start making releases again. I wonder if I should call the next release Recast & Detour 1.5 or 1.9?</div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com5tag:blogger.com,1999:blog-1272803659321539598.post-40799847428341351802011-03-25T03:17:00.000-07:002011-03-25T03:42:16.733-07:00Detour API ChangesOnce you update to R289 you will notice that the Detour API has changed a bit. This change was necessary so that Detour could support multiple layers per tile location.<br /><br /><div>Here's quick migration guide you should follow when switching to the latest code.</div><div><br /></div><div><b>1)</b> There is no need to remove the padding of the polymesh coordinates before the vertices are passed to dtCreateNavMeshData(). So if you had code, like this before, <b>remove it</b>! If you are not using tiles, this does not apply.</div><pre><code><span class="Apple-tab-span" style="white-space:pre"> </span><span class="Apple-style-span" >// Remove padding from the polymesh data. TODO: Remove this odditity.<br /><span class="Apple-tab-span" style="white-space:pre"> </span>for (int i = 0; i < m_pmesh->nverts; ++i)<br /><span class="Apple-tab-span" style="white-space:pre"> </span>{<br /><span class="Apple-tab-span" style="white-space:pre"> </span> unsigned short* v = &m_pmesh->verts[i*3];<br /><span class="Apple-tab-span" style="white-space:pre"> </span> v[0] -= (unsigned short)m_cfg.borderSize;<br /><span class="Apple-tab-span" style="white-space:pre"> </span> v[2] -= (unsigned short)m_cfg.borderSize;<br /><span class="Apple-tab-span" style="white-space:pre"> </span>}</span><br /></code></pre><div><b>2)</b> Since the polymesh data is not offset anymore, you can feed the polymesh bounding box directly to navmesh builder:</div><pre><code><span class="Apple-tab-span" style="white-space:pre"> </span>rcVcopy(params.bmin, m_pmesh->bmin);<br /><span class="Apple-tab-span" style="white-space:pre"> </span>rcVcopy(params.bmax, m_pmesh->bmax);<br /></code></pre><div><b>3)</b> I made the BV-tree building optional as it is not needed for tiles which has just a couple of polygons. To keep the old behavior, you need to add this line to your navmesh build params:<pre><code><span class="Apple-tab-span" style="white-space:pre"> </span>params.buildBvTree = true;<br /></code></pre><div><b>4)</b> When you access tiles, you need to specify tile <b>x</b>, <b>y</b> and <b>layer</b> indices. If you don't use layers, just pass 0 (zero) as layer index. For example:<pre><code><span class="Apple-tab-span" style="white-space:pre"> </span>m_navMesh->removeTile(m_navMesh->getTileRefAt(tx,ty,<span class="Apple-style-span" >0</span>),0,0);<br /></code></pre><div><br />That's it. The navmesh data number bumped so you will need to rebuild your data too.<br /></div><div><br /></div><div>I also removed the test code from Sample_TileMesh. From now on the Sample_TempObstacles will be my sandbox. The code to build tiles at runtime will live under DetourTileCache. It is all a bit of mess still, I'll keep you updated about the progress.</div><div><br /></div><div>I think I will move back to numbered releases so that I can keep the SVN a bit dirty when I need to. Once the temp obstacle stuff is done, I think it is time to release Recast & Detour 1.9.</div></div></div><div><br /></div><div>Oh, and I updated the VC project too!</div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com2tag:blogger.com,1999:blog-1272803659321539598.post-27039158186722286012011-03-20T12:02:00.000-07:002011-03-20T12:12:26.215-07:00Simulating Human Collision Avoidance<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZNFlH4OHejU2xutWhVvR3UwXVUElrCsQ8cdck2w56SB4u5GCcBM9sLHxCWgiqOEUJ5rF036h2Iq2KF0Y_XIaIUlqEyN6ShUpKx7VRB7VarwssZiLx_38dsWsyZhKwgg6t2tlTjv3vC0EC/s1600/Screen+shot+2011-03-20+at+9.01.04+PM.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 276px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZNFlH4OHejU2xutWhVvR3UwXVUElrCsQ8cdck2w56SB4u5GCcBM9sLHxCWgiqOEUJ5rF036h2Iq2KF0Y_XIaIUlqEyN6ShUpKx7VRB7VarwssZiLx_38dsWsyZhKwgg6t2tlTjv3vC0EC/s400/Screen+shot+2011-03-20+at+9.01.04+PM.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5586239954810534770" /></a><div>There were many good collision avoidance papers published last year. One trend that I saw already when I was preparing my <a href="http://gameaiconf.com/">Paris Game AI Conference</a> presentation last year was that the next step in the human like collision avoidance will come from inspecting motion capture data.</div><div><br /></div><div>One of my favorites from last year was <a href="http://people.cs.uu.nl/ioannis/hca/index.htm">A Velocity-Based Approach for Simulating Human Collision Avoidance</a> by Karamouzas & Overmars. Technically their solution is very close to the sampling based RVO, but there is one very important difference; quoting the paper:</div><div></div><blockquote><div>Our analysis, though, focuses on the <i>predicted time to collision</i> between interacting participants and the deviation from their desired velocities, whereas they studied the effect that the <i>minimum predicted distance</i> has on the participants’ accelerations.</div></blockquote><div>In practice it means that they did bunch of measurements with real people and noticed that the velocity sampling range depends on the predicted time of impact.</div><div><br /></div><div>That is, if the agent things it will hit something 3 seconds in the future, it is likely to adjust the speed and angle just a tiny amount, but if the collision is imminent, the agent may adjust the velocity a lot. The plot at the top of the post shows how the sampling range changes based on the predicted time of impact.</div><div><br /></div><div>This is tiny detail, but very important one. The resulting animations (accessible via the link above) look pretty good too.</div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com8tag:blogger.com,1999:blog-1272803659321539598.post-88268648509445545002011-03-17T10:38:00.001-07:002011-03-17T10:43:36.621-07:00Bulletstorm is Using Recast<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgexZ3EWEbFRwcQZsTM-EEzi0tfyCGd6SX58JrU-hJFenXLHzMM52O-YAjfZgNeQbPjbx1y1OrIXSAPOZAyJVa6h3B4hFcY_aMZTM8KFFj-Ke3ZXuI-E5NHcuYiM3p22Hp2t9i1XwvrHdYP/s1600/bulletstorm.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 333px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgexZ3EWEbFRwcQZsTM-EEzi0tfyCGd6SX58JrU-hJFenXLHzMM52O-YAjfZgNeQbPjbx1y1OrIXSAPOZAyJVa6h3B4hFcY_aMZTM8KFFj-Ke3ZXuI-E5NHcuYiM3p22Hp2t9i1XwvrHdYP/s400/bulletstorm.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5585104814074496498" /></a>Much to my girlfriends disappointment, I just got my copy of Bulletstorm today! She was expecting the courier to bring her a fragrance from Venice and UPS brought this gory awesomeness from Warsaw instead.<div><br /></div><div>Congrats to Mieszko and the gang at People at Can Fly for shipping such a great game! And thank you for mention me in the credits :)</div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com10tag:blogger.com,1999:blog-1272803659321539598.post-81231314745332002472011-03-12T11:38:00.000-08:002011-03-12T11:53:36.940-08:00Layers in Detour<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfdFvGj-ijm2v20qsgaU0rVPoSRzVLO0i-GcYAKR3setsrXLBcWStx9rdQZaQsawoX_fb8guXBvWkFXT42rzFFrCWIj5F4LTpa1F9diNybCBug46_OJ41TecCq6qKuNezoRiM3AFyxjMxG/s1600/layer_detour.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 254px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfdFvGj-ijm2v20qsgaU0rVPoSRzVLO0i-GcYAKR3setsrXLBcWStx9rdQZaQsawoX_fb8guXBvWkFXT42rzFFrCWIj5F4LTpa1F9diNybCBug46_OJ41TecCq6qKuNezoRiM3AFyxjMxG/s400/layer_detour.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5583280297905034802" /></a>Well.. this may look like a unmeasurable step in no direction at all, but it is indeed layered tile pieces working in Detour! There are a lot of rough edges to be fixed, but I'm glad I got this far.<div><br /></div><div>Some things were a bit painful to debug. Looks like the tile stitching needs to be redone at some point in the future. As you can see in the above picture, the navmesh is missing a detail mesh. I have an idea how to make a semi good detail mesh really quickly.</div><div><br /></div><div>Anyways, once I check in the stuff it means that Detour and Recast APIs will change a bit. I will write migration guide once I have polished the code a bit.</div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com9tag:blogger.com,1999:blog-1272803659321539598.post-6457707847442328792011-03-11T11:54:00.000-08:002011-03-11T12:09:46.504-08:00Temporary Obstacle Processing Overview<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjLpINguf71vNkGDOFQVnWCdVkb9McSUL0LSk2F1IcnXXQOi9dB3ZNGwW-L2MW6i9w-w0FziJg09FVvbnsdxLWdPdSUFHH0onNjYdDQwbVUpfbiq9w1UBizipnwvUGzfncI55ef_U94KUgg/s1600/temp_obstacle_process.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 314px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjLpINguf71vNkGDOFQVnWCdVkb9McSUL0LSk2F1IcnXXQOi9dB3ZNGwW-L2MW6i9w-w0FziJg09FVvbnsdxLWdPdSUFHH0onNjYdDQwbVUpfbiq9w1UBizipnwvUGzfncI55ef_U94KUgg/s400/temp_obstacle_process.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5582913279872169026" /></a>I was <a href="http://twitter.com/#!/clodericmars/status/46167024354869248">asked on twitter</a> to give an overview of the navmesh generation process. Click on the above picture to see what happens when a temporary obstacle is added.<div><br /></div><div>What is missing from the picture is the logic that triggers tile updates when an obstacle is added or removed. I have not quite figured that all out. The plan is to have one class that allows you to add and remove temp obstacles, and then you update that class each frame, give it a time quota, and it will figure out which tile layers to update based on the obstacle shape and finally update the navmesh.</div><div><br /></div><div>The tile layers will be always updated all the way from the compressed data, so adding or removing an obstacle will be the same process, but the temporary obstacle set used to build the layer will be different.</div><div><br /></div><div>The obstacle shapes are expected to be expanded by the agent radius.</div><div><br /></div><div>Each obstacle marks an area type into the grid. This means that you can punch holes or just mark certain areas depending on what you do. My plan is to support a couple of obstacle types, like extruded polygons and circles, but nothing prevents you from inventing you own shapes too! Maybe you can have some kind of cone to describe a line of fire of an agent, or a sphere which describes the radius of an explosion.</div><div><br /></div><div>I'm quite excited about the performance I measured <a href="http://digestingduck.blogspot.com/2011/03/heightfield-layer-progress-pt-3.html">earlier today</a>! The final step is to connect it all to Detour. It will be mostly boring bookkeeping coding on how to connect the tiles and such.</div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com3tag:blogger.com,1999:blog-1272803659321539598.post-52487500381535250202011-03-11T03:16:00.001-08:002011-03-11T03:35:47.143-08:00Heightfield Layer Progress pt. 3<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEixrSBtYjhMZhDLnFPuZhNjpFsTKVSIqyWoLOcSsXyGSYyAfhORHat65_FuYMYzl_KdDroKNUHhmJfLB2QTxXBFRUL1rAgF7Xw_E-yIpWRbNKfe4x6tE0aT87U4aITzdVEFid-bnyIInii8/s1600/Screen+shot+2011-03-11+at+1.12.43+PM.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 299px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEixrSBtYjhMZhDLnFPuZhNjpFsTKVSIqyWoLOcSsXyGSYyAfhORHat65_FuYMYzl_KdDroKNUHhmJfLB2QTxXBFRUL1rAgF7Xw_E-yIpWRbNKfe4x6tE0aT87U4aITzdVEFid-bnyIInii8/s400/Screen+shot+2011-03-11+at+1.12.43+PM.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5582779665500559970" /></a>Today was scary day. I finally added some data collection to my heightfield layer code I've been working on recently. The numbers look super promising!<div><br /></div><div>I measured the time to build navmesh for the above level, which I have been using earlier too. For build time and memory usage I measured the time that it takes to build a layer of navmesh from existing heighfield layer (rcHeightfieldLayer if you are familiar with the code). That is pretty much the bare bones of the process at runtime. I did not measure the time to rasterize temp obstacles yet.<br /><div><br /></div><div>I tested with a 32x32 tiles. The build time for a single tile layer varies from 0.01ms to 0.2ms, 95% of the tiles take less than 0.1ms. As expected there is some variation from run to run in the timings. The build process for one tile takes less than 15kB of memory. I'm really happy about that as all data could potentially fit in cache.</div><div><br /></div><div>The data that needs to be stored in the memory takes 545kB for the above level, which compresses to 77kB using fastlz. What is interesting here is that the memory requirements for layers is smaller than for <a href="http://digestingduck.blogspot.com/2011/01/compressed-heighfields.html">compressed compact heightfield</a> even if there is a lot of waste in the layers. I think the win comes from the fact that there is no need for additional information about the layers.</div></div><div><br /></div><div>Here's the complete <a href="http://sites.google.com/site/recastnavigation/layer_test_data.txt">test data in numbers</a>.</div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com1tag:blogger.com,1999:blog-1272803659321539598.post-77759809339987243432011-03-06T08:00:00.000-08:002011-03-06T08:04:43.087-08:00Removed Old SampleFYI – I removed the <i>Solo Mesh Tiled</i> sample which has been obsolete for quite some time already. It does not provide any advantage over using tiled mesh all the way through and has become a slight maintenance burden. I will keep the merge functions around for the time being, but eventually they might go away too.Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com2tag:blogger.com,1999:blog-1272803659321539598.post-37174160196168099082011-03-06T05:07:00.001-08:002011-03-06T05:32:59.993-08:00Heightfield Layer Progress pt. 2<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjv9W-Bs2BaDoZSbLihwnCoSSc7Ktrfk3fJIrehiBX1dXTHzYKjyoqKfritCGTTlJeYs4nY40wrHiM-HFZHbxBtYUdnX6xEu36CwO74xSXPb8arGfFTw8P3xG-PszC_nWHLRn0Pp6DwPCp9/s1600/layermesh_progress.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 159px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjv9W-Bs2BaDoZSbLihwnCoSSc7Ktrfk3fJIrehiBX1dXTHzYKjyoqKfritCGTTlJeYs4nY40wrHiM-HFZHbxBtYUdnX6xEu36CwO74xSXPb8arGfFTw8P3xG-PszC_nWHLRn0Pp6DwPCp9/s400/layermesh_progress.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5580953044226431010" /></a>Firstly, I apologize the current state of the SVN. Some files are missing from the VC project, some headers have messy stuff and there are some extra stuff in the UI. I often like to check in stuff I'm working on when I get to a certain point so that I can revert if the new direction is a dead-end. It usually takes few tries to get something figured out properly.<div><div><br /></div></div><div>The above image show some phases of the new navmesh generation procedure. It is very much like the original Recast version, but I added some extra constraints to the data.</div><div><br /></div><div>Firstly, the voxelized heighfield is first split into 2D layers. These layers are stored in compressed form. This 2D data can be packed more easily than 2.5D data as neighbour data is more often similar.</div><div><br /></div><div>When the navmesh of a a portion of the level needs to updated, for example when a temporary obstacle is added or removed, the layer data is uncompressed the obstacles are rasterized, and the navmesh of that layer is rebuild.</div><div><br /></div><div>The layer structure ensures that each uncompressed layer takes the same amount of memory during process, which helps to manage the memory layout. Less data also means more local memory access, which should speed things up too.</div><div><br /></div><div>Secondly, I have limited the max tile size to 255. This means that I can use bytes as coordinates and further reduce the memory requirements. The same magic number limits the maximum number of regions per layer too.</div><div><br /></div><div>I'm currently sweeping through the code and try to remove allocations as much as I can. The code will require allocations, but I have been able to remove a lot of reallocs, which makes the code more linear allocator friendly. My goal is to make the memory consumption below 64k, on tile sizes between 32-64, maybe even 32k is possible for the sizes closer to 32x32.</div><div><br /></div><div>There are some things left to do on the generation side, like removing those excess vertices. I think I'll wait until I finish those things before I dare to measure the performance.</div><div><br /></div><div>After that I will need to figure out how to change Detour to support multiple layers. My current plan is to store each tile at location (x,y,layer), where the layer is just some number you decide yourself. This should nicely allow other kinds extra navmesh layers too, like overlapping streaming sections, etc.</div><div><br /></div><div>Also, another nice side effect is that the layer generation process will make 2D navmesh generation much easier. Basically you could just feed in an image and get navmesh out.</div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com3tag:blogger.com,1999:blog-1272803659321539598.post-35175418721345293232011-03-03T23:48:00.001-08:002011-03-03T23:59:30.765-08:00Insomniac is using Recast for Resistance 3Just heard interesting news from GDC. Insomniac is using Recast to create navmeshes for Resistance 3! <a href="http://aigamedev.com/">AiGameDev.com</a> has <a href="http://forums.aigamedev.com/showpost.php?p=67431&postcount=5">coverage</a> of the talk on their forum.<div><br /></div><div>I was kinda expecting this based on the screenshots in Mike Acton's <a href="http://macton.posterous.com/unfinished-usability-is-not-random">slides</a> his unfinished usability presentation :)<div><br /></div><div>I would love to know how they arrange the data so that they can do pathfinding on SPU. Their future directions look very much inlined with my ideas, i.e. rebuild tiles on SPU for sleeping temporary obstacles.</div><div><br /></div><div>Can't wait to hear the whole presentation.</div></div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com4tag:blogger.com,1999:blog-1272803659321539598.post-40572828064480221442011-02-26T06:35:00.001-08:002011-02-26T06:46:26.018-08:00Heightfield Layer Portals<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhYydlzPk1CzGsqxheqYvPdOesVhTakI-czYM2EO7KYgsm33FJ7b9vUQvniPIghlOm2VzNWi2IxlFeet7-xzVMpkCXiB2IzP0Kynwv5zFeDhDxppf4RpLIZd_k_iTxBQuJUy2p8dJgpU400/s1600/layer_borders.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 374px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhYydlzPk1CzGsqxheqYvPdOesVhTakI-czYM2EO7KYgsm33FJ7b9vUQvniPIghlOm2VzNWi2IxlFeet7-xzVMpkCXiB2IzP0Kynwv5zFeDhDxppf4RpLIZd_k_iTxBQuJUy2p8dJgpU400/s400/layer_borders.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5578006996471101186" /></a>I worked today a bit on the layers again. I was trying to find the minimal data that needs to be stored. There were a couple of cases which required a bit more thinking.<div><br /></div><div>For example should the layer contain that extra border or not? I decided that it should not. That required me to store the edges which may lead to a connected layer and it also means that the obstacle will need to be expanded by the agent radius, but that is something I was planning to do anyways.</div><div><br /></div><div>It turned out to be a good choice to dig up the portals anyways. Now it is possible to calculate a hierarchical graph based on the portals only. The way the layer partitioning is done makes sure that the connections between two layers are always axis aligned. This makes things a lot easier and robust. As difference to the connections between navmesh tiles, with layers there can be a portal in the middle of a tile too. I will need to add support for this in Detour later.</div><div><br /></div><div>I think I'll add a bit more info for the portals, for example which portals are connected to each other within a single layer.</div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com0tag:blogger.com,1999:blog-1272803659321539598.post-61189332477847511382011-02-25T03:23:00.001-08:002011-02-25T03:41:31.063-08:00Heightfield Layers Progress<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj8ehKXjdwr0cHJA2ZYRTwTUf8TlKBb11owh4SqSsbIQPpDnfCgUFYCfdMp4DxO7vV504GoL_NW-4llugmdCkgoI6T5Lt8u0ig1QYN8Y3YVOBzzRYpGNKnuK6NALGY9LYkt_993D7fMHnkq/s1600/recast_layers.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 328px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj8ehKXjdwr0cHJA2ZYRTwTUf8TlKBb11owh4SqSsbIQPpDnfCgUFYCfdMp4DxO7vV504GoL_NW-4llugmdCkgoI6T5Lt8u0ig1QYN8Y3YVOBzzRYpGNKnuK6NALGY9LYkt_993D7fMHnkq/s400/recast_layers.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5577586453582028834" /></a>I have been working on the heightfield layers a bit more. As <a href="http://digestingduck.blogspot.com/2011/01/2d-grids-for-win.html">I've explained earlier</a>, I'm trying to make the temporary obstacle processing much faster by decomposing the walkable area into 2D layers.<div><br /></div><div>Then the temp obstacles will be rasterized onto those 2D areas and build into pieces of navmesh. The idea is to try to limit the changes of a temporary obstacle processing to as local area as possible and to speed up the generation process in general by making the input data simpler.</div><div><br /></div><div>Each layer stores area type and 2D heighfield. The area types should compress really well with RLE, and it should be possible to compress the heighfield using a simple linear spline fitting. Add LZ compression on top of that and the aux data for generating new tiles should not be a huge burden anymore.<br /><div><div><br /></div><div>Interestingly, this layered heighfield data is also something that can be used to make 2.5D <a href="http://www.cs.ualberta.ca/~mmueller/ps/hpastar.pdf">HPA*</a> (the papers so far have used 2D data). If someone out there is up for the challenge, let me know and I'll help you to decipher the data Recast creates.</div></div></div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com1tag:blogger.com,1999:blog-1272803659321539598.post-8200099550567166492011-02-22T04:32:00.000-08:002011-02-23T07:34:05.071-08:00Iterating Cube Vertices, Edges and Faces<div>This keeps haunting me. There must be an awesome way to arrange the data so that you can do a simple for loop and iterate over all cube vertices, edges and faces. I'm sort of after something you could use in matching cube like algorithms to fetch data from a sample grid without having to use lookup tables.</div><div><br /></div><div>Vertices or sample offsets are easy:</div><div><br /><br /><pre><code> for (int i = 0; i < 8; ++i)<br /> {<br /> const int dx = i & 1;<br /> const int dy = (i>>1) & 1;<br /> const int dz = (i>>2) & 1;<br /> printf("%d: %d,%d,%d\n", i, dx,dy,dz);<br /> } <br /></code></pre><br /><br /></div><div><span class="Apple-tab-span" style="white-space: pre; ">A</span>ssuming that you have 3 values per sample, one along each axis, the following code can be used to walk through all the valid edges:</div><div><br /><br /><pre><code><br /> for (int i = 0; i < 12; ++i)<br /> {<br /> const int ax = (i >> 2) & 3;<br /> const int as = (4-ax) >> 2;<br /> const int bs = (5-ax) >> 2;<br /> const int v = ((i&1) << as) | ((i&2) << bs);<br /> printf("va=%d vb=%d dir=%c\n", v, v|(1<<ax), "XYZ"[ax]);<br /> }<br /></code></pre><br /><br /></div><div>But... I'm not satisfied, there must be a cleaner way.</div><div><br /></div><div>I once figured out how to procedurally draw a cube with just one for loop, but I cannot remember how to do it anymore, IIRC it used rotating sequence of XYZ, ZXY, YZX somehow, much like how you calculate cross products.</div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com13tag:blogger.com,1999:blog-1272803659321539598.post-68843404601591226422011-02-13T10:48:00.000-08:002011-02-13T11:08:16.281-08:00Very Temporary Obstacle Avoidance pt. 2<iframe src="http://player.vimeo.com/video/19859732?title=0&byline=0&portrait=0" width="400" height="225" frameborder="0"></iframe><br /><div><br /></div><div>I exposed my <a href="http://digestingduck.blogspot.com/2011/02/very-temporary-obstacle-avoidance.html">previous attempt</a> at local obstacle avoidance to some more challenging situations and oh boy did it explode! For example the above shows really complicated case, which looks really innocent. There are a couple of problematic cases.</div><div><br /></div><div>Firstly, the obstacles that reach to the sides are problematic to handle. The sides needs to classified regarding the goal direction (blue) but they can reach back to over 180 degrees in certain cases. I had to make a lot of special case code to make sure to detect when right is still right even if it is on left side. Yeah!</div><div><br /></div><div>The second problem case is how to handle the terminator nodes (those red dots, which indicate that an obstacle touches a wall). Initially I thought just to use the line to goal to split detect if a terminator is left or right. It worked well for many of my tests, but there are cases like in the above video, where the terminator changes sides!</div><div><br /></div><div>So anyhow, hours of hacks and tricks later, I thought I'd give up a little.</div><br /><iframe src="http://player.vimeo.com/video/19895239?title=0&byline=0&portrait=0" width="400" height="225" frameborder="0">&amp;amp;lt;/iframe&amp;amp;lt;br&amp;amp;gt;</iframe><div><br /></div><div>Few days later, I thought why not try the old <a href="http://digestingduck.blogspot.com/2010/03/local-navigation-grids.html">local grid pathfinder</a> I made some time ago. I took <a href="http://www.devmaster.net/codespotlight/show.php?id=17">a well tested rasterizer</a>, changed it to support convex polygon and in no time I had working prototype of local obstacle avoidance in DetourCrowd.</div><div><br /></div><div>The code is pretty simple to understand, it should be pretty fast too. I did not test the impact yet, but my previous tests indicate that it is fast.</div><div><br /></div><div>The local pathfinder operates on the yellow area you can see in the video. If the blocking obstacle is larger than that, path cannot be found. The navmesh and the obstacles are updated every now and then, I could potentially use lower update rate too.</div><div><br /></div><div>There a couple of problems still left to be solved. Firstly, the currently is no reliable way to detect that the agent is stuck. Secondly, in some cases the local pathfinder finds a bit different route, which leads to flicker.</div><div>_</div><div><br /></div><div>We'll see how this all works out. I hope to speed up the navmesh temp obstacle baking a little. It is still the best choice. I think the local grid path planner could be usable for simpler games or those who cannot spend the extra memory required by the tile cache.</div>Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.com12