Author Archives: admin

Cover location detection

22 Mar
admin 0

I’ve been working on top-down angled action idea. For this indie project, I wanted to find safe cover locations for enemies to hide (crouch) behind and shoot from.

On my first attempt at a solution, I tried using the unreal EQS system, then my own implementation (picking points, raycasting to see if they hit an object at a crouching level, and raycast to see the point was clear at gunfire level.

This produced ‘okay’ results. But it presented a few problems. I’d have to implement additional checks for enemy sizes. Implement additional traces to checks if a spot was reserved/occupied. It also would miss spots (as shown by the red spheres) depending on how the checkpoints lined up. I’m also testing a lot of locations.

This solution just had too many issues, so I decided to take a different approach.

My second solution, add a simple box collider to valid cover spots, on a cover only trace channel. To accomplish this, I extended the UBoxComponent class creating UAreaCoverMarker and implementing a GetCoverLocations function. This function takes two parameters, the player’s location, requesting enemies width and returns a TArray of structs that contain each cover points FNavLocation and their ForwardVector (vector pointing towards the cover object.)

To discover the best hiding side, I calculate the colliders top for vertices, and sorted them by distance from the player.

A = Furthest vert from player
B = 2nd Furthest from player
C = 3rd Furthest from player
D = Closest to player

AB will always be the furthest side from the player. The direction of A-C will point away from the BoxCollider and towards the area, we want to test for cover space.

Step 1: Taking the enemies width I divided the length of AB, to calculate how many hiding slots could potentially exist on this line.

Step 2: Using the direction A-C I located the starting and ending test points.

AB

StartPoint = Move A in the direction of A-C by 1/2 the enemies requested width.
EndPoint = Move B in the direction of A-C by 1/2 the enemies requested width.

 

 

 

Step 3: Move the StartPoint 1/2 the distance of enemy width towards B. (this is the center of our first test.

Step 4: Check if this spot has a collider on the ReservedArea channel below it towards the ground. If not proceed.

Step 5: Check if we can cast this point onto navmesh (setup a query tolerance.) if we can the point is valid!

Step 6: advance this test point by the enemies width towards the EndPoint, repeat for the number of hiding slots calculated at Step 1.

As you can see below, this doesn’t exactly work great for large rectangles or cubes. Depending on the player’s location, sometimes enemies should hide behind AC too!

 

Hmm, isn’t the other side safe too.

 

To fix this, let’s turn to the late great Heron and find the side AC.  If the Triangle PlayerAC has a greater area than PlayerAB, include AC in the solution.

Step 7: Repeat Step 2 – 6 for the line AC, if the area of triangle PAC > area PAB

[PAC (green triangle) > PAB (red triangle)]

 

 

 

 

 

PAC area < PAB area

 

 

 

 

Custom latent – delayed Blueprint function in C++

30 Nov
admin 0

I wanted to make two functions with delays to assist BP scripting of logic. One for dialog and one for item interaction. The one I’ll cover here handles dialog.

My goal: Make a function that accepts dialog parameters, waits for a user response and returns the player’s selection. (Additionally, make a breakout which flows execution based on the player’s selection.)

I couldn’t find any help online when writing this function. So I crept through engine code. Unreal has a LatentActionManager held by UWorld. You can get its reference from GetWorld->GetLatentActionManager()

Using this I made a c++ class derived from FPendingLatentAction and put our own logic in it.

 

 

 

Here is the BP functions header:

Here is the function’s definition:

What happens above, we grab the LatentActionManager and make sure it currently isn’t running a task for this object and pass it our custom latent task, along with our custom latent tasks construction params.  InteractionInfo is a custom struct with the players choices, and PlayerSelection is an enum of the possible responses the player can have.

Let’s look at my custom FPendingLatentAction derived class:

Constructor:

I create a callback (I send a self reference to the actor who called this function.) Once the player has selected input, I push a response to this delayed action.

One could also poll from the UpdateOperation. The tick/update function notes a value has been set and completes the task.

If you want to break out the response use the ExpandEnumAsExecs UFunction specifier:

 

 

Grid based Broad-Phase Collision detection

4 May
admin 0

This method is best suited when uniformly or very similarly sized objects are being tracked. If objects do not differ much in size each cell should be the size of the largest object. This makes it so only the center of each object needs to be tracked.

 

Example below:

PSizeOverlap from shapes in non-adjacent cells is impossible if the cells are as large or larger than every shape tracked. If shapes end up being larger however overlap is possible and we need to track the shape in every grid cell it exists.

 

If the cells are smaller that the largest object overlap will exist as demonstrated below.

If thisTooLarge happens we need to track more than just an objects center (covered below.) There are a few ways to solve this, increase the grid size, use another detection system or track more than just an objects center.  Increasing the grid size can have unexpected consequences.

 

If the cells are too large, there will be an excess of results in each cell eliminating efficiency and increasing computation to or towards On^2. As the picture to the left demonstrates. TooSmallEvery object in each cell will have to be checked against each other for overlap.

Spatial grid tracking can be accomplished using a hash table or a 2/3d array.  A 2d array is fairly straight forward.

The next post will cover creating a hash table, generating a cells key (from coordinates), finding neighbors and detecting overlap.  Followed by a post on creating bounding shapes to cover objects that are larger than a grids cell size.

 

 

Octree Post

5 Mar
admin 0

The only differences between an Octree and a Quadtree is an additional axis.  This post will cover bounding box checks; for Tree psuedo code and structure breakdown go to my Quadtree page.  Please note an interactive example is below for this tree structure.  For spheres and cubes (circles/rectangles in 2d) it’s always quicker to check intersections by comparing centers and length or radius.  For simplicity I only store a bounding boxes length and center.

 

To test if a point is inside a bounding box. Take the absolute value of the distance between the point and this boxes center, if this value is less than 1/2 it’s length (I times the distance by two because I don’t store half lengths).  If it’s true for every axis this point is inside.

 

To test if bounding boxes overlap.  Take the ABS of the distance between the two boxes (times by two or compare to their half lengths) and check if that value is less than the boxes combined length.  If it is, they overlap.

 

OctreeBoxTo find the child node a point falls into can be solved with three axis checks.  Example of how I arranged the nodes to the left (the cube that isn’t visible is 101.)

(Please note interactive example below takes about 30 seconds to load):

Quadtree Post

5 Mar
admin 0

This is the first of a three posts covering trees and using them to partition space.  Each post will contain an interactive demo (bottom of the page.)  This post will cover Quadtrees, followed by Octrees and k-d trees.

A Quadtree is a useful tool when one needs to store and search for points in 2d space. In a quadtree a node is either a leaf or parent with four children.  QuadTree Paritioning

Node composition:
The example to the right shows a Quadtree with a root node, one parent node and 7 children.  When using them to divide space we can see the root node in red has four children.  The spaces they represent are show with the bisecting blue lines.  Three of these four children are leafs, with only one of these leafs containing a data point.  The child representing the SE region is not a leaf node, it is a parent and has four leafs.  Two of it’s child leaf areas are shown by the blue and yellow lines.  Of these leafs, three have data points.  In a quadtree a node can have only two forms; a parent with four leafs or a leaf with no children.  A leaf does not always contain a data point, it can represent an area with no data.

A node must contain the following:
It’s four children (if they exist) North West, North East, South East, South West regions.
A field to store its data point (X,Y)
And a struct,class or fields to store its bounding box (the area it contains usually represented as X,Y coordinates)
Optionally you can include a reference to it’s parent

Here is the class from the interactive example.

 

Point insertion:
Inserting a point is done recursively.  First check if the point falls within the root nodes boundary box.  The steps following are duplicated until it is placed, starting at the Root node.

Does this node have children;

    • Yes – find the child region this point falls into and send it to the node. [side note to find the area we use the bounding box each node has.  My bounding box holds three things a nodes center X, Y and it’s length.  If a points X is greater than this nodes X center it falls in the East region, if it is greater than the Y center it falls to the North region. I had 01 represent NW, 11 NE, 10 SE, 00 SW.]
    • No – does this node contain a data point yet?
      • Yes – Make this node a parent, create its four children and pass the new point and this nodes previous data point to the new children who will use this recursive process to place
      • No – store this point on this leaf.


Finding the closest data point :

Now that points are stored, one of the useful ways to use a quad tree is searching for points within an area, or finding the point closest to a coordinate without comparing the distance of every point within a tree.  The logic below covers finding the closest point to a location.  It can also be used to find every point within an area.

This search uses the following three objects
AlreadySearched – Hash set of already searched nodes
FoundLeafNodes – Queue to hold the nodes to check distance on [optional]
SearchBoundingBox  – The BB area we need to search
SearchPoint – the X,Y coordinates we are trying to find the closest data point to
ClosestNode – the closest node found

    Step 1 recursively dive to the lowest leaf whose bounding box contains the Search Point

  • Check if this leaf contain a datapoint
    • Yes – Store this node as our ClosestNode and find the length from this point to our SearchPoint (node, add this node to the ClosedSet.)  Construct a SearchBoundingBox centered at the Search Point with this length.  We will use this to test if any other leafs contain points within this box that are closer.  A box will cover some areas that do not need searched, it is however simpler and faster than a circle.
    • No – go to this leafs parent, one of its descendants will contain a leaf with data.  Recursively breadth search every node downward and store them in the FoundLeafNodes queue (also store every node we visit in our ClosedNode hash set) [Note the FoundLeaf queue can be eliminated by tracking the best result and testing as leafs are reached.]
      • Take the queue of found points and search through them to locate the closest node.  Take the length of this node and use it’s length to construct a bounding box from the center of our SearchPoint
  • Now visit every node within our SearchBoundingBox to confirm we have the closest datapoint.   We can check this with a simple bool test : (Mathf.Abs(BoxA.BisectX – BoxB.BisectX) * 2 < (BoxA.Length + BoxB.Length)) && (Mathf.Abs(BoxA.BisectY – BoxB.BisectY) * 2 < (BoxA.Length + BoxB.Length)).  Starting at the root node recursively build the FoundLeafNodes queue.
    • This node is not in our AlreadySearched set and overlaps the SearchBoundingBox
      • Yes (add it to the AlreadySearched  set)
        • Is this a leaf node
          • Yes
            • If it contains data add it to the FoundLeafNodes queue
          • No
            • Repeat the test for all this nodes children
      • No
        • We have already searched this node, ignore it and it’s children
    • Once the recursive search finishes and all the valid leafs have been added to the FoundLeafNodes queue, test all these points to find the closest node, and return it.  (Don’t forget about the ClosestNode we used to construct our bounding box, it could be the closest.)


Interactive Example (please note takes about 30 seconds to load):

When using the interactive example below to search for a node, that the green box represents the SearchBoundingBox  used to test for the closest node. You can see how this is needed as diving down to the node which contains our SearchPoint will not always return the closest result.

GG Pathfinding – Path Occupancy Bitmask

20 Aug
admin 0

64 bit to flag node occupancy:

One of the first items I have experimented adding to help improve pathfinding was to add a ulong to each nodes.  Each bit represents a slice of time. I flag the bits based off unit speed, noting when it would occupy this node. This seems to help movement with few entities:

great with 8

 

The first unit to move gets priority. Each path calculation the unit requesting a path shifts the nodes bitmasks based off the time it was set, to the current time and checks if it’s occupied when it would arrive.  If it is, it adds the cost of moving diagonally to the total cost (or whatever one want’s.)  This seems to be a good indication if the unit should avoid this nod or if its cheaper to wait.

 

 

Mass MovementAug 16, 2015 13:30

With several units many started to go backwards before going forwards and/or take very inefficient paths when they should wait.  Search time is also increased.