In this week's update, I like to talk about a new enemy type I've been working on for quite a while - the sniper - a sly and cunning enemy that threatens the protagonist with her undodgeable snipe attack and anti-gravity movement. In the following paragraph, I will briefly explain why I've decided to add this character into the world of 《Drifting》; the obstacles I've encountered during the development of her unique feature; the solution I came up with as well as the pros and cons of my solution; finally, a short video demonstrating the confrontation between the protagonist and the sniper.
Why make the sniper?
The core experience of 《Drifting》 is the traversal and combat in 3D space, the various arsenal the protagonist posses all aims to help her achieve that goal, however, the same cannot be said for enemies in 《Drifting》. Most enemies are bound to a 2D plane, even if some of them seem to "fly" around in 3D space, they are just following pre-specified path nodes without respecting the surrounding geometries. The lack of a third dimension for enemies' movement system makes the combat of 《Drifting》 felt more inclined to 2.5D instead of 3D (players move in 3D, yet, their focus is still on a 2D plane most of the time). In order to provide a combat experience that is closer to 3D, I've decided to make a special type of enemy that can traverse in 3D space. By making this mechanical change, hopefully, I could improve the overall combat experience.
A suitable approach for 3D pathfinding
To develop a 3D pathfinding algorithm is no doubt a huge task that requires a lot of time and effort, sadly, UE4 did not come with an officially supported 3D pathfinding system. Before deciding to develop my own algorithm, I've searched on the web and found some fascinating plug-ins that could do solid fully-featured 3D pathfinding, however, the ones I've found are all based on 3D-grid, which could generate a huge overhead given the size of my level; the complexity of the algorithm - although adequate to get the job done - seems overkill if I only have one type of enemy that utilize the system. After few days of contemplation, I've decided to resort back to a path node approach combine with some line traces to enable the sniper to walk on a 3D plane while (somewhat) respecting the surrounding geometries.
The spider movement algorithm
Before explaining my approach, I want to make it clear that, this algorithm is by no means a general solution to 3D pathfinding - this is just a simple way to make actors walk on predefined path nodes with some respect to the plane it is traversing.
(in this case, point A is NOT on ceiling, to go from point A to B, first project A to ceiling to get point C; move from A to C; project point C to the plane of point B to get point D; move from C to D; since, D and B are at the same plane, simply move from point D to B)
To go from point A to point B, do the following:
- check if A and B are on the same plane
- if true, move to point B
- if false, check point A is on ceiling
- if true, project point A to the plane of point B to get point D; move from A to D (goto step 1. with point A replaced with point D)
- if false, project point A to ceiling to get point C; move from A to C (goto step 4 with point A replaced with point C)
The critical part of this algorithm is the determination of whether two points are on the same plane. I use the dot product between the vector AB and the normal of plane A (the plane where A resides) and compare it to a threshold value of 0.01; if the absolute value of the dot product is greater than the threshold, two points are NOT on the same plane; if the absolute value of the dot product is smaller than the threshold, two points reside on the same plane. A threshold that is too high will cause two points that reside on different planes but with long-distance mistaken to be residing on the same plane; A threshold that is too low will cause unnecessary movements between two points that are on the same plane.
(after developing the algorithm, the final step is to place the spline path inside my level,
which is the easier part)
Below are some pros and cons I think is crucial to know before adopting this algorithm:
1. easy to implement
2. cost of performance do not scale up when increasing the size of the level.
1. cannot have "holes" or "bumps" in plane
2. requires a ceiling
3. can only work in convex space (for line trace to work properly)
Here is a short demonstration of how the sniper behaves in actual gameplay.
(notice at 00:07, the protagonist avoided the undodgeable snipe attack by performing a dash move;
the dash move has a 0.3sec window of invincibility that ignores all incoming damage
- a trick that is very useful yet difficult to execute in heated combat)
I hope you enjoy reading my article and I wish you a Merry Chrismas and a Happy New Year! :3