Crafting 3D User Interfaces for the Web

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).

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.

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.

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.

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.

Loose Navigation Grid Prototyping

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.

Path Planning in Dynamic Worlds

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.

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.

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.

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.

Loosing Up the Constraints

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.

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.

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. 

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.

The Prototype

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.

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.


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.

Ludum Dare 23

Last weekend I took part in Ludum Dare game development compo. I've been jealous to Jetro 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.

The game I made for the compo is called Gingerbread Kingdom, it is kind of a mix between Carcassonne, Tower Defence and Rampart.

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 (Babauta 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.

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.

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.

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.

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.

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 :)

So when I finished my "all nighter" around 2 am the first day, I had my basic game done.

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.

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.

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.


The ideas that spawned the day after when I saw people actually play the game were:

• make tile rotation instructions in bigger, bolder, blinkier and fancier text 
• no scrolling, make the gamefield fit on screen
• add level of increasing difficulty
• could be procedurally generated
• ramp up difficulty based on enemies and terrain (water tiles)
• better indication which tiles are ready to fire
• lasers!

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.

Demopaja Sources

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:

• Demopaja_050508.zip

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.

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.

[EDIT] You can treat the code public domain, some libs and snippets have their own licenses, treat them appropriately.

Choosing random location on navmesh

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.

dtStatus findRandomPoint(const dtQueryFilter* filter, float (*frand)(), dtPolyRef* randomRef, float* randomPt) const;

dtStatus findRandomPointAroundCircle(dtPolyRef startRef, const float* centerPos, const float maxRadius, const dtQueryFilter* filter, float (*frand)(), dtPolyRef* randomRef, float* randomPt) const;

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.

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.

I wanted to avoid allocations, so I started to look for a "streaming" random selection algorithm. The solution turned out to be Reservoir Sampling. I modified it a bit to make it consider the area of a polygon.

Area weighted reservoir sampling looks something like this:

poly = nil
areaSum = 0.0
foreach p in polygons {
    area = p.area()
    areaSum += area
    if (frand()*areaSum <= area) {
        poly = p
    }
}

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.

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.

The code was committed in R331.

Loose Navigation Grids

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.

A Grid

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.

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.

Automatic Exploration

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.

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.

In addition to the flood fill, overlap of neighbor grids is used to filter new grid location generation.

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.

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.


Path Planning

I have not yet implemented this phase, but this is how I think it should be done.

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.

Movement within one grid is calculated using simple grid path planner. 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 Way Portals. 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.


Future Improvements

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 Paris 2011 persentation.


Conclusion

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.

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:

• Local: 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.
• Hierarchical: 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.
• Dynamic: 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.

I think this is the way to implement path planning in 2012!


Download prototype and code (OS X):

• navtest.zip

Path Replanning

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.

Prerequisite
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.

Movement Request
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.

Path to Target
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.

Path Following
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.

API
This could lead to following interface between the high level logic and the movement request.

struct MovementRequestCallback
{
 // Called after path query is processed.
 // (Path result accessible via ag->corridor)
 // Return true if path result is accepted.
 virtual bool result(Agent* ag) = 0;

 // Called when path is blocked and
 // cannot be fixed.
 // Return true if movement should be continued.
 virtual bool blocked(Agent* ag) = 0;

 // Called when the agent has reached
 // the end of the path trigger area.
 // Return true if movement should be continued.
 virtual bool done(Agent* ag) = 0; 
};

bool dtCrowd::requestMovement(int agent,
 const float* pos, const dtPolyRef ref,
 MovementRequestCallback* cb);

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.

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.

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.

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).

What do you think?