Mouse Brain

[Macha]

I thought it's time to learn python, so I made a mouse brain that can find cheese on a map and avoid obstacles.

Set the start position, move the cheese, place an obstacle and she will find a path to it. (Geometry edges are allowable paths). The red line represents the calculated path. It jumps during the animation. That's because the obstacle is animated to display the path finding only.

If I have time I'd like to make it more sophisticated and implement the A* search algorithm.

Edited January 13, 2010 by Macha

[Macha]

The mouse now looks cuter and is cleverer.

There is a penalty to choosing already visited points (mouse memory!). This avoids the path cycling between 2 points.

[pclaes]

nice little exercise! Does it run fast?

[Macha]

nice little exercise! Does it run fast?

Well...for a map with 500 scattered points, it takes about a second to find the path. I don't know if that's fast or not.

[asnowcappedromance]

hey Macha,

nice one!

I also started learning Python recently, would you mind to share your hipfile?

I'm still struggeling with the basics in the cookbook, what was your approach to learn Python inside

Houdini? Would be nice to get some tips!

regards,

Manuel

[Macha]

If anybody reading this here knows the A* algorithm:

I *think* I can get it to work but I can't figure out how to extract the path. Eventually I reach my goal and I got a dictionary with all searched nodes and the parents they came from but I'm not sure how to reconstruct the path from this.

edit: If I understand it correctly, many more nodes have been examined than there are in the final path, so how do I know which node-parent-lineage to choose.

Edited January 15, 2010 by Macha

[Macha]

Oh...I think I got it...I can trace backwards...

[Macha]

WOHOO! I did it! AI in Houdini!

This (A-Star) is said to be one of the best path searching algorithms. It guarantees the shortest path and is very flexible because you can tweak speed/accuracy.

The obstacle in my example transfers an attribute onto the grid. It is blended so that is why sometimes shorter paths nearer the obstacle are ignored.

The first video shows the mouse taking the best path (notice that she doesn't venture into the U like my previous -less intelligent- mouse would have done)

The second video shows the algorithm in action as an obstacle moves around.

Really really really chuffed with this! I thought it was too big a challenge for a long time.

Edited January 15, 2010 by Macha

[pclaes]

very cool stuff! Now that you have achieved this, can you make it work in the volume too? It should be possible right? Scatter points in the volume, triangulate them and find the path? That's really cool as you could have creatures crawl over objects in 3d (represented by pointclouds), too often I've been stuck with having to use the uv's for this type of thing. Having a triangulated approach in the volume would be awesome. Also you could probably extend this to include waypoints. So it has to go through a certain area before going to the cheese.

I think you should try to scale it so you got something working for 20 mice, potentially obstructing eachother's paths.

Really good progress!

[Macha]

very cool stuff! Now that you have achieved this, can you make it work in the volume too? It should be possible right? Scatter points in the volume, triangulate them and find the path? Having a triangulated approach in the volume would be awesome. Also you could probably extend this to include waypoints. So it has to go through a certain area before going to the cheese.

I think you should try to scale it so you got something working for 20 mice, potentially obstructing eachother's paths.

Really good progress!

I think going through a volume should pose no problem as long as the points are connected by polys with edges (that's how I search the neighbors). Otherwise I'd have to rewrite the function that finds neighbors. I think isooffset can give me a 3d mesh connected by polys. I'll have to test this next week.

For 20 mice should be possible, if tricky. In any case, you could always make 20 different mouse-brain nodes... Avoiding each other's path would be very difficult for me to do in the algorithm itself but once I have the basic paths it should be possible to make the mice wait or speed up as they approach each other, similar to what I did in those blobs in an earlier post.

The waypoints are quite an interesting question though. Dunno if I can do that...have to think about it for a while...

[Macha]

As you can see it works for 3d paths as well.

With the waypoints...I'm thinking if I could let the goal be a list instead of a number, and once it has reached the first item in the list it exchanges the goal with the second, etc.

[pclaes]

Cool update again!

Perhaps include a radius along with the list of goals. Almost as if they have to go trough a "keyhole" and you can specify the scale of the keyhole.

I think one of the important things for this is perhaps to try making it adaptive. Especially if a mouse has to "run around the corner of a box". Having more points where there is higher curvature would provide better curves (similar to a bevel operation) around sharp edges. If you have the time... make a simple model of a staircase and see if you can make your mouse go down the stairs.

Even more advanced would be to do updating adaptive path sampling through an octree. Great stuff so far!

[Macha]

I implemented a waypoint, as you suggested. Trickier than I thought but now we have an adjustable weight to it that attracts the mouse's decision.

This is slightly different to a radius in that its effect also depends on where the waypoint is in relation to the main target. I haven't tried it but it should be possible to paint this, so that you could make preferred paths.

About that path jumping, it's because I am not considering a moving target/obstacle,waypoint at the moment. I haven't given it much thought yet but perhaps blending the calculated curves could get rid of it. (if it moves, it's a newly calculated curve every frame)

Next I should tackle that upscaling problem. Hmmm....

[Nibbler]

it should be implemented by SESI in H in network_view to smoothly moves curves between nodes connections, in very large scenes it would be so much helpfull, anyway cool project Marc

[Macha]

The code is still very slow for larger maps but I managed to increase speed by an order of magnitude by pre-calculating neighbours and adding a (pre-calculated) distance weight.

The picture below shows the difference in how the algorithm searches the map. The paths are different because adding a distance weight makes the algorithm more efficient but less exact (but good enough for most purposes)

[Macha]

I finally managed to get real waypoints into mouse's path-finding brain. (Quite a struggle for my brain).

I also made the setup simpler, quicker and more robust. It is now possible to just drop nulls into the scene. Naming them start, goal, way1, way2, etc and they will automatically be picked up by the script so that it is easy to set new waypoints.

I'm considering adding confetti bombs when the mouse gets to the cheese.

The path in the picture below doesn't look like the shortest possible. There're 2 reasons for this: The underlying pathfinding grid (invisible) is not square and there is a distance penalty added to the heuristic (speeds up the searching) that makes the mouse initially head out towards the target regardless of "bestness". You can see that behavior nicely on the back right flag.

As for the jumping paths, I did some quick tests and they can be eliminated with a chop network.

Edited January 22, 2010 by Macha

[Macha]

A mouse climbing down stairs, avoiding an obstacle, and passing waypoints. It took a little over 2 seconds to find this path.

[pclaes]

again very nice progress!

I guess in terms of speed up if you have waypoints, every path "from - to" a waypoint could be branched off in a separate thread. I am not familiar with that A* searching algorithm, perhaps a different datastructure could help speed things up too?

[Macha]

again very nice progress!

I guess in terms of speed up if you have waypoints, every path "from - to" a waypoint could be branched off in a separate thread.

Argh, stop putting those ideas into my head.

I have no experience in threading, at all, but maybe it is possible? The code has 2 number-crunching parts: building a traversable graph, and searching a path through it.

The latter part looks something like the following.

for every pair_of_goals:
    while node != goal:
        search path

So, I'm thinking that every bunch of while-loops in the for-loop can be a different thread because they search the path between the waypoints and are thus independent of each other. As long as I can figure out the order in which they return the paths I can stitch them back together into the main, finished path.

What do you think? Any pointers, links, ideas?

[pclaes]

Just sharing my thoughts... and look at how far you've already pushed this, so you can clearly handle it .

I have used threading a bit with python, but not directly within houdini. You should indeed be able to branch off some of those independent calculations. Have a look at this little example on how to get started if you wanted to get further into it:

http://www.wellho.net/solutions/python-python-threads-a-first-example.html

Perhaps there are other thread friendly pathfinding or sorting algorithms too.

It is also my feeling that there could be an adaptive solution which could potentially speed it up a lot when dealing with a lot of points on your grid. Imagine you first have a rough grid, 10x10. You can now run your algorithm on this rough grid. Big obstacles will already block some points, smaller ones will be ignored. Per bucket you will now have a point where the path comes in, and a point where the path goes out (so you have a start and a goal per bucket). Each bucket get's subdived into another 10x10 grid. Now the smaller object start to show up on the 10x10 grid. If there is no start or goal in a bucket it can be excluded from the calculations. If you were to subdivide again, you will get another level of accuracy. If this works, then you discard buckets fairly quickly, and this should make a difference on detailed pointclouds. Eventually you will then hopefully end up with a highly detailed path.