Update: This week I improved the hit detection. Until last week all hits (swords, arrows, etc) were performed against rectangles (AABBs). This works well enough for most things due to the rectangular shape of a lot of the objects and creatures, but it performed very poorly against other shapes. Here are a few objects (a tree and a 'horse') for which rectangles do a poor job:
You can attack the empty space in the top-left of the horse and the system would detect a hit, likewise for the shaded areas in the tree. You can alleviate this by shrinking the hitbox, but then you have another problem: not all parts of the sprite will respond to attacks.
For more precise hit detection you need to use more precise shapes. I decided to use polygons, but you could also use multiple rectangles or even circles. (This is for geometric hit detection. You could also do image-space / pixel-perfect hit detection but that requires an entirely different approach.) Box2D (the physics library used in Moonman) supports hit-tests against convex polygons, and so it was just a matter of Creating those polygons and then Implementing polygon hit-detection.
Creating Polygons From SpritesDue to the number of entities in the game, I decided to automatically generate polygons for all the large sprites. For each sprite this involved:
(1) Finding a contour / bounding-polygon which surrounds the entire sprite
(2) Simplifying the contour to use a small number of vertices
(3) Partitioning the polygon into it's convex parts
(1) was done using OpenCV, which has a tonne of interesting image-processing features. In some cases I had to dilate the image to generate suitable contours (as the thin parts of sprites sometimes caused multiple contours to be created.) The actual functions I used were findContours, dilate, and then approxPolyDP which performed step (2).
To do step (3) I first triangulated the polygon and then greedily joined each triangle to its neighbour, checking for convexity along the way. This is a fairly naive approach but it does the job for now! (One bad thing about it is that it produces non-optimal and fairly random partitions.) When all this was in place (via a Python script), my toolchain then outputs the polygons. Here they are superimposed over the spritesheet:
You can see the horse is modelled much more precisely now, and that large gap in the top-left is now mostly gone. Theoretically you could make this as precise as you like, but you'll have to pay for it in run-time efficiency. And here they are, imported into the game. The tree is modelled quite well.
Polygonal Hit-DetectionWhen taking a swipe at a tree or horse, the game performs a number of raycasts along the length of the weapon. If any of these intersect the hit-shape of the object then a successful hit is recorded. Before this week the rays were just cast against a single hitbox, but the hit-test now performs a few steps:
Cast a ray against all bounding boxes
For each successful test, either:
(1) Do another raycast again each convex polygon in its sprite, or
(2) Do a raycast against a smaller hitbox
Step (1) is only performed if the shape is big and if the graphics quality is medium or higher. This means that for small shapes or if you're on low render quality, you don't pay for the high-precision hit tests. There are a lot of horrible details omitted (like Box2D not like collinear points in a polygon), but that's the basic system. I hope that with this increased accuracy the game will feel more cohesive -- there's something odd about hitting empty space and having a hit register.
Here I am testing the system by flashing a polygon if it is hit:
Another interesting detail is the each animated sprite has a set of polygons for every frame. This will allow us to change the general shape of the creature, say by dropping the horse head to take a drink, and for hit-tests to still work on that different shape. Here you can see the different polygons for each frame of the horse walk animation.
In other news, the arrows have been annoying me for a while. They often wouldn't stick into the ground, or would slide along the ground, or would get stuck in odd angles ... so I cleaned quite a lot of that up.
Community
