Wednesday, December 23, 2009

Stumbling Towards the Holidays

After a small hiatus, I've been grinding off my to-do list. The first item was to finish the local navigation proto.

Firstly, I implemented static segment obstacles into my testbed to create more realistic scenarios. The outcome was badly stuck agents. It was way worse than I expected it to be.

After adding the graph based steering helper from my previous post, things got immediately much better. You can see that in action at the end of the video. The obstacle graph is the extra blobs, connected by arcs. The connected islands are formed and each labeled using simple graph flood fill. It would be necessary to tesselate the edge segments as in the video, but I was testing original idea and they just kinda got left out there.

Instead of the graph walk, I use similar method as in Oriented Visibility Graphs to calculate the new desired movement direction (longish white arrow in the video). The cool thing is that my version it can handle many kinds of local minimas, but not all.

The result from the obstacle graph is somewhat present in the TOI sampling too, I wonder if it would be possible to combine the two algorithms.

I hope I can squeeze out few evenings during the holidays and finish off and release the proto.

Before that happens, thank you for all you who have followed and commented this blog, I hope to get good pace of postings coming up next year, too. Until then,

Merry Merry, Happy Happy and New Year too!


  1. Mikko: one obvious thing I see in these videos, is that the circles don't simply stop.

    If you look at real people navigating around each other, its quite usual for them to simply stop and turn sideways to allow more space for others to pass. Or to actually move behind a stationary obstacle to allow others to move quicker.

    Is there some way of adding that kind of thing into the work your doing now?

  2. Phil, I noticed similar thing. Based on how I tune the parameters I get a bit different results, but the agents never really do stops, unless that is the only option.

    Choosing the velocity is pretty hard, and I took the same assumption as this paper [1] and it seemed to generate good results on simple cases with open space, the results are a bit too hectic to my taste on tight cluttered areas.

    In the example scenario, there are two choke points, where "in real life" might not try to over take. Or based on example by others, they might use the "left going" and "right going" openings.

    I want to make it first as robust as possible and as fast as possible. Currently sometimes some agents gets trapped behind wall of others.


  3. Merry Xmas!
    Thanks for all your help.


    Got dynamic tile method working. Next thing to do is serialize nav data and then onto IK foot placement.

    Try and get same result as this:-
    (but I doubt I'll manage)

  4. I read about methods of a foot placement in the book "Advanced game development with Programmable Graphics hardware". They suggest to analyze animations of the foot bones, build special curves and change curves as you need. And how do you want to implement it?

  5. Merry christmas and happy new year.

    You've made life interesting for alot of people.