Mutatis Mutandis: screenshots and commentary

guyr on 2011/09/18 21:37 of Team Mitzi
— edited on 2011/09/18 23:05

Here are some examples of turtle geometry. The resulting procedurally-generated objects are supposedly easy to mutate:




Here is an example of the walk area to which the avatar is confined. Clicking outside of it takes the avatar to the nearest possible point within the walk area.


Here is what happens when obstacles are in the way. The graph below contains all vertices of the walk area (including the hole) and the avatar's source and destination points. The blue lines indicate paths that pass completely within the walk area (and are thus edges in the graph). The green lines indicate the shortest paths from the avatar's source point (in the lower right quadrant) to all other points in the graph (computed by Dijkstra's algorithm). The avatar chooses the shortest path from source to destination.


This is just the very beginning of keyframes for animation. At this point I retired.


G.

(log in to comment)

Comments

Cosmologicon on 2011/09/18 21:44:

Wow, very interesting. Did you implement that pathfinding algorithm yourself? I needed something like that for a game a while back. I think it would be very handy if you could distribute the code. Ideally if you could handle circular obstacles as well, and have a variable that controls how closely the thing can get to a wall (which can be implemented by simply expanding all the walls inward by this amount).

guyr on 2011/09/19 13:10:

Yes. I simply wrote a ridiculously naive implementation of Dijkstra's graph search algorithm based on the corresponding Wikipedia page. The trick is to properly construct the graph. The vertices are chosen as I explained above [all vertices of the walk area (including "holes" - internal obstacles) and the avatar's source and destination points]. Each two vertices are connected by an edge if and only if the straight line between them passes entirely within the walk area. This is easily calculated with shapely. The weight assigned to each edge is the actual geometric distance between its vertices.

The only other less-trivial point about this path-finding implementation is what to do when the user-specified destination point is outside of the walk area. I found that the best results are obtained by selecting the closest point within the walk area and using it as the actual destination. This is easily calculated with shapely's project method. Note that this is not the same as clipping the path to the destination point by the walk area.

I'm not sure what you mean by circular obstacles. Do you mean something other than the hole that can be seen in the walk area?

Regarding closeness to walls: I think the simplest solution is to manually construct the walk area so that it takes that margin into account, but you can also easily shrink the walk area programatically with shapely's buffer method.

G.

Cosmologicon on 2011/09/19 14:40:

Ah yeah the hard part for me was constructing the graph, so it's good to know about shapely. Thanks!

The problem with manually constructing the walls to show the walkable area is that it forces all your game objects to be the same size. If your game doesn't need large and small enemies, this should work fine. But if you do need different sizes and you do this, either the large ones will be sticking out of the walls, or the small ones will be running into invisible walls.

The matter of circular obstacles is trickier. By circular obstacle I mean a hole that's circular rather than a polygon. You can approximate it with a regular polygon with a large number of sides, though, so it's not really essential. I would have used it in my project, but it probably wouldn't come up in most projects. The way you do it is in your graph construction, you place edges that are tangent lines from points outside the circle to the circle itself. Between any two circular obstacles you place edges along the four mutual tangent lines. I haven't looked into shapely yet, so it may have an easy way to do this.

Thanks again for posting!

guyr on 2011/09/19 15:54:

Interesting. I guess for such a scenario it makes sense to dilate the walk area per "walker".
BTW, wouldn't your "enemies" constitute obstacles in themselves which other enemies would have to take into account? Perhaps this page would interest you.

Regarding circular objects:
1. The tangents idea is nice. I don't think shapely will help you much. It doesn't support continuous curves (like circles), and I don't see a simple way of using it to calculate tangents. However, I think it is not too difficult to calculate the tangents manually with a little effort. Also there are other geometry libraries (with which I'm not familiar) which may help: euclid, CGAL-python, pygeo and maybe more.
2. Approximating circles with high-resolution polygons will work, but it might make the Dijkstra algorithm too slow (because the graph will grow exponentially).
3. I think for most applications the best solution is to approximate circles with low-resolution polygons (as low as possible). Since this geometry is only used for walking, not rendering, it doesn't have to be pixel-perfect. Unless your enemies move extremely smoothly, the difference would probably not be perceptible.

G.

Cosmologicon on 2011/09/19 17:51:

Yeah I agree that for most applications a circle can probably be approximated by an octagon or something. In my case I had a large fountain in the middle of the room, which would have been noticeable if it was replaced with an octagon in the back end. Still I probably should have just used a 40-gon or something.

Thanks for the link! I've always used a hack to treat units running into each other. I've never taken unit positions into account when pathfinding. I'll have to give that version a try.