Dev diary 2: Creating the map for the game from scratch

Dear diary,
In Part 1 I've covered some of the ideas that could be implemented for the map logic. And even did a basic implementation with grid cells.
This time I am going to build a slightly harder solution based on polygons.

Some plans

The goals to implement are:

• To define and split the map in sectors of NxM length.
• Each sector containing information regarding what obstacles are in it's bounds.
• Player position can be converted to it's corresponding sector.
• On movement the players position and direction forms it's own segment (A -> B).
• Find the intersection with any segment in the current sector, null if none.
• Improve visual debugging.

Also keeping an eye on possible features:

• Dynamic obstacles, ones that would be intersected in a separate loop. A use case would be spells like "wall of ice". An optimised version would check only for segments within a specific radius from the player.
• Trigger zones - spaces that are not obstacles but entering their bounds would dispatch an event.

A tiny bit of code

For starters some code to build basic shapes and to draw them in the Unity Debug.

public struct Segment
{
    public FPoint P1 { get; private set; }
    public FPoint P2 { get; private set; }
    public Segment(FPoint p1, FPoint p2) { P1 = p1; P2 = p2; }
}
****
public struct Shape
{
    public List<Segment> Segments { get; private set; }
    public bool Convex { get; private set; }
    public Shape(List<Segment> segments, bool convex) { Segments = segments; Convex = convex; }
}
****
public static class ShapeUtils
{
    public static Shape Circle(
        FPoint center,
        float radius,
        int division,
        float degree = 0f
    )
    {
        double step = 2 * Math.PI / division;
        var initialOffset = degree * Math.PI / 180;

        Segment[] segments = new Segment[division];

        FPoint current = new((float)(radius * Math.Sin(initialOffset)), (float)(radius * Math.Cos(initialOffset)));
        FPoint start = current;
        for (var i = 0; i < division; i++)
        {
            var a = step * (i + 1) + initialOffset;
            FPoint next = i != division - 1 ? new((float)(radius * Math.Sin(a)), (float)(radius * Math.Cos(a))) : start;
            segments[i] = new Segment(current.Plus(center), next.Plus(center));
            current = next;
        }
        return new Shape(segments: segments.ToList(), convex: true);
    }
}

Along with that come some additional structs and extensions, such as FPoint which is basically a Vec2. But a custom implementation to keep it agnostic from the engine.

Next, drawing each segment around the player object will results in this:

Which are done by 3 and 16 divisions of the circle, with adjustment to the player rotation.
Now that a basic shape is implemented and seems to work properly I can proceed with other shapes such as Line and Rect.

A small fast forward. (This took me a couple of evenings of short sessions)

The image above shows the improved debug rendering of the map with shapes and additional text info for each sector. For now I only show the coordinates and the count of obstacles in the sector.

Detecting if there is a shape in the sector.

We need to split our "world" into smaller chunks. Why? So that we don't check for collision with every shape on every frame/action.

As an example we have a circular shape on our map. It may span across multiple segments.
The naive approach is to take every point of the shape and check if it's coordinates are in range. But that's not good enough.

In case if the obstacle is bigger than the sector, the sector does not have any point inside of it - thus the naive algorithm is not working.

The better solution is to traverse the path of each segment of the shape and generate the coordinates it goes through. Each coordinate will correspond to its sector (adjusted for sector scale)

Repeat this for every shape. Find the coordinates, add the shape reference to each corresponding sector. Create a data structure out of that. This is our simple map.

The tricky part to remember is to account for the points that are on the borders of the sectors.

Detecting collisions

Now that I have my map I want to move my character and stop him when he reaches an obstacle.
I've had several solutions in mind.

• Tick based. Move the character every tick/frame bit by bit, check for collisions and stop if there is an obstacle.
• Interpolation based. Calculate the state/position based on the time elapsed from the start of the movement.

I've wanted to try the second solution long ago so I went with it. Here is the basic idea:
Once there is an intent to move (player input, AI decision) a state object is created which describes:

• - State (idle, running, casting)
• - Start position, timestamp
• - Speed of action (speed of running, speed of casting)
• - End goal (end position, cast target)

Based on this, the engine logic (aka frontend) can calculate the state for every frame. With this we do not need to run a background loop of moving the objects around and performing collisions checks every frame.
The trick will be to pre-calculate those collisions only once when the intent to move is created.

The logic to find the end point of the movement is such:

• Get delta of movement (X and Y values) from the input manager. -- If zeroes - return
• Get current X and Y positions from the game logic state.
• Get target end positions (current position + delta)
• Traverse the path from current to target (Segment A)
• Based on the path find a set of coordinates and their sectors from the map
• Find all segment intersection of Segment A and shapes in the sectors in the path of movement
• Find the shortest intersection from the current position - this is the end point

Some links that helped me:
Code to find intersection of two segments

Point rotation formula

Point projection onto line

With this the character now can move and hit the walls. Unfortunately this stops him completely. In the next diary entry I will explore how to make the character move "along" the wall using the point projection.

I'll see you next time, my dear diary.

• Max