How to determine/display possible movements in turn-based grid game

[sinelin]

Hi,

I'm still quite a newb when it comes to C++ (or programming in general) and SFML so this is a project more for my personal learning and interest than anything else.

I've been stumped for a while now on how to implement a way to properly determine the possible movements in a turn-based grid game.

At first, I've implemented possible movements to be something like this:

(click to show/hide)

Basically what happens is that when you click the banana button (just testing for now), the possible grids you can click on to move to gets filled with the colour yellow. After you click on one of those grids, the grids will stop showing and the sprite on the left will move to that grid (always x first, then y; I don't intend to make diagonal movements possible for now; also note that the sprite on the right doesn't do anything other than occupy a grid at the moment). Once the sprite finishes the movement, the banana button will appear again.

I threw in a check so that you cannot move to a grid already occupied by another entity and thought it was fine until I realised that while you cannot move to an occupied grid, you can still move through them:

(click to show/hide)

However, before I start working on trying to make it so it moves around the occupied grids instead of right through them, I needed to make sure the possible grid movement being shown is correct. There shouldn't be a yellow grid on the right of the non-moving stick entity since it would take more than 3 grids to get there (that is if you dont move through him or diagonally).

I've been stumped on this for a long time, tried multiple different ways to implement this logic but I cannot come up with anything that works properly or consistently. I've tried to write nests and nests of IF statements instead of using loops , but it got way too messy to manage and I feel that there has to be an easier way.

Eventually, I've stripped it all down to movement in a straight line. If the grid is blocked, further grids beyond no longer gets shown:

(click to show/hide)

This works fine, but obviously I want to also display grids beyond just a straight line. What would be a simple solution to implement this logic?

For reference, below are my current code for implementing the grids. I apologise in advance if they lack clarity, since I'm still quite a newb and may adopt practices and conventions that are not optimal. However, I've inserted comments and tried to explain what I did.

(click to show/hide)

#include "TurnBasedBattle.hpp"
void TurnBasedBattle::drawGrid()
{
    if (displayMoveGrid)
    {
        std::string tGridKey = gridMap[playerDrawList[0]->gridPosition].id; //player's current grid id

        int tGridX = gridMap[playerDrawList[0]->gridPosition].getGridPositionX(); //grab player's artificial grid x-coordinate 1~14
        int tGridY = gridMap[playerDrawList[0]->gridPosition].getGridPositionY(); //grab player's artificial grid y-coordinate 1~9
        //std::cout<<"Position: "<<tGridX << ","<<tGridY<<std::endl;

        int movePoints = 5;
        int gridWidth = 14;
        int gridHeight = 9;

        int northLimit = movePoints;
        int eastLimit = movePoints;
        int southLimit = movePoints;
        int westLimit = movePoints;

        /***To make sure you do not move off the Gridboard***/
        while ((tGridY - northLimit) < 1) --northLimit;
        while ((tGridX + eastLimit) > gridWidth) --eastLimit;
        while ((tGridY + southLimit) > gridHeight) --southLimit;
        while ((tGridX - westLimit) < 1) --westLimit;


        showPossibleGridMoves(eastLimit, "east");
        showPossibleGridMoves(westLimit, "west");
        showPossibleGridMoves(southLimit, "south");
        showPossibleGridMoves(northLimit, "north");

    }
}

void TurnBasedBattle::showPossibleGridMoves
(int & ref_dirLimit, std::string ref_dir)
{
    GridStatus * ptr_gridstatus;
    ptr_gridstatus = &gridMap[playerDrawList[0]->gridPosition]; //pointing to the the grid the player is on
    for (int i = 0; i < ref_dirLimit; ++i) //ref_dirLimit is the number of movement in that direction possible
    {
        /**
         *  grabDir() allows access to grids next to the grid itself (north/east/south/west)
         *  every GridStatus contains pointers to north/east/south/west of the grid itself
         *  with nullptr assigned when there is no grid in that direction
         **/
        if (ptr_gridstatus->grabDir(ref_dir)->isBlocked() == false) //if not blocked, show next grid;
        {
            ptr_gridstatus = ptr_gridstatus->grabDir(ref_dir);
            showGrid(*ptr_gridstatus);
        }

    }
}

void TurnBasedBattle::showGrid(GridStatus & ref_gridstatus)
{
    ptr_mainWindow->draw(ref_gridstatus.mark);
    mouse_position = sf::Mouse::getPosition(*ptr_mainWindow);
    if (ref_gridstatus.checkMouse(mouse_position)) //if clicked
    {
        displayMoveGrid = false; //stops showing the display grids
        gridMap[playerDrawList[0]->gridPosition].clear(); //gridPosition no longer occupied by player

        //change the player's new gridPosition so that he gets moved in another cpp file...
        playerDrawList[0]->gridPosition = ref_gridstatus.id;
    }
}

 

Thanks for anyone who can help me this.

-Sine

[Laurent]

If I understand what you want, what you need is a flood fill algorithm.

You start at the player position, and collect all its non-occupied adjacent cells (there should be max 4). Mark all these adjacent cells as occupied now, add them to the final list of reachable cells, and recursively apply the same process on all of them. Stop at the 3rd recursion level if you want to limit moves to 3 cells. Your final list of reachable cells contains what you want.

Basically, what it does is to expand the reachable area by 1 cell at each iteration, from all the available cells collected at the previous iteration. It's quite simple.

See "flood fill" on Wikipedia / Google for more details if you don't understand the algorithm.

[Critkeeper]

If you need speed you could do a geometric approach.

Just treat the map the character walks on as a plane. The range of the movement corresponds to the height of a point above the plane (in the 3rd dimension).

The point coincides with the tip of a cone, and the code passes through the plane so that the intersection is a filled circle.

Its like shining a light from a point onto a map.

If you want to restrict movement based on occupied squares, that is tantamount to putting an object in front of the light to darken certain squares.

So far the algorithim is just creating a circle and seeing if the center of the square exists inside the circle or not, and subtracting some squares afterward based on whether not it is already occupied.

This isn't yet accurate though. Imagine creating a set of possible squares that you can move to, and then without any further checks you would just be able to move from the center to near the edge, then double back and go through the center to the other side for example-- that clearly isn't what you want.

If you employed this algorithm as is you'd see strange defects like not having the range to move all the way to the bend of a U shaped hall just yet, but as you move close enough to make it to the bend, all of a sudden you have the range to go all the way to the other end of the hall!

If the range is 1 then the algorithm as is is 100% accurate.

If the range is 2 or more then the algorithm is only 100% accurate if there is no blocking objects.

So essentially an object in one square may block movement in one or more squares, by preventing you from reaching them because you have to weave around in order to get to it and you don't have the range to do that.

So the trick is to devise an algorithm that takes as its input:

the set of all squares ( a filled circle based on your range )
a subset that set-- the set of all blocking squares ( individual squares blocked by terrain or units )
a square at which the character is located (not really, since ranged based movment in the case for your game is figured as a circle and a circle has one unique center)

As output it produces a single set:

 a superset of the set of blocking squares which is also a subset of the set of all squares-- it represents the squares that cannot be reached.


And you just take that output and negate it with the set of all squares to produce the set of squares your character CAN reach.




A square can either be blocking or non blocking. The area of a circle is proportional to the area of a square, for some proportionality constant. That means that the total number of squares is proportional to n^2, where n is the number of squares on one side-- in other words it is proportional to the radius of the circle.

Each square is either blocked or non blocked, so there are 2^s combinations, where s is the number of squares.

Putting that together, there is X = 2^(K*n^2) combinations, where K is roughly equal to 3.141592... divided by 4 and n is the radius of the circle.

This is a continous function, and you have a discrete problem, so keep in mind this is just an approximation that only becomes very accurate as n increases. It still gives a good rough estimate for n in the neighboorhood of half a dozen or so.

At very low values the continuos function is an innaccurate approximation for two reasons. First, it cannot approximate the discrete nature until there are sufficiently many squares to bring it closer to its limiting behaviour. Second, a "range 1" indicates that you have access only to the square you are in, and that you can only move to that square. A "range 2" indicates you can move to 5 squares-- the one you are in or the 4 adjacent to it. A "range 3" means you can move to a total of 8 different squares, or perhaps 12. The point is that going from range 1 to range 2 is a quadrupling, and going from range 2 to range 3 is less than a quadrupling.

We already know the function for the number of squares goes as n^2, so this major discrepancy between the continous model and the discrete reality is excarcebated by the differences at low numbers. Fortunately for numbers greater than 3 or 4 it becomes a decent approximation.

For n = 4.5 ( diameter of 9 squares, so a range of 5 if you count range of 1 as being able to move to only the square you are currently in )

X = 61330

This makes it small enough to precompute a comprehensive table for range 5 movement. You can just apply the table twice to do range 10 movement. Or 3 times for range 15.

If the table is too large and you want to trade memory size for number of times spent accessing the table, you can just use n = 3.5 or n = 2.5.

If you want a more accurate number then make a pixel circle by hand and count the number of pixels. Now raise 2 to that power. For range 3 (by my way of counting range) it is 13, so 2^13 = 8192

[sinelin]

If you need speed you could do a geometric approach..........................

Thank you for the descriptive answer. However, I must admit that I do not have the faintest idea on how to actually go about implementing that. Mathematics has not been my strong point. Can you please provide a small example of this?

If I understand what you want, what you need is a flood fill algorithm

You start at the player position, and collect all its non-occupied adjacent cells (there should be max 4).................

Thanks for the idea. I have looked into wiki and have tried different ways of implementing this. But I still can't seem to get it to work correctly.


Once again, thank you both for your help. I cannot even fathom how a geometric approach to this would be. So I've went and redone the function several times trying to  to implement a recursive function akin to what a flood fill algorithm may be like (except of course, mine doesn't work). My current code follows this logic (or at least I think it does!)

(click to show/hide)

I pass the player' gridposition and the player's movementPoints into this function...

showPossibleGridMoves(GridPosition, int movementPoints)
1. If grid north to the player is out of bonds, return.
2. If grid north to the player is occupied, return.
3. If the northern grid is not already added to the drawing container of pointers for grids, then:
   Add the northern grid to the drawing container for grids.
4. Step 1-3 is repeated using loop for east/south/west.

5. Subtract 1 from movementPoints
6. if movementPoints is greater than zero, then:
     showPossibleGridMoves(north grid, movementPoints)
     showPossibleGridMoves(east grid, movementPoints)
      showPossibleGridMoves(south grid, movementPoints)
      showPossibleGridMoves(west grid, movementPoint)

My actual code is

(click to show/hide)

void TurnBasedBattle::showPossibleGridMoves(std::string ref_gridId, int ref_moves)
{

    GridStatus * ptr_grid;
    ptr_grid = &gridMap[ref_gridId];
    sf::Vector2i tmp_gridPosition(ptr_grid->getGridPositionX(),ptr_grid->getGridPositionY());

    std::string tmp_gridKey;
    bool isOverLimit;

    for (int i = 1; i <= 4; ++i)
    {
        //std::cout<<i<<std::endl;
        switch (i)
        {
        case 1:
            tmp_gridKey = formGridId(tmp_gridPosition.x, tmp_gridPosition.y - 1);
            isOverLimit = ((tmp_gridPosition.y - 1) < 1);
            break;
        case 2:
            tmp_gridKey = formGridId(tmp_gridPosition.x, tmp_gridPosition.y + 1);
            isOverLimit = ((tmp_gridPosition.y + 1) > 9);
            break;
        case 3:
            tmp_gridKey = formGridId(tmp_gridPosition.x + 1, tmp_gridPosition.y);
            isOverLimit = ((tmp_gridPosition.x + 1) > 14);
            break;
        case 4:
            tmp_gridKey = formGridId(tmp_gridPosition.x - 1, tmp_gridPosition.y);
            isOverLimit = ((tmp_gridPosition.x - 1) < 1);
            break;
        }

        if (isOverLimit) return;
        else if (gridMap[tmp_gridKey].isBlocked() == true) return;
        else if (gridIsDrawn(tmp_gridKey) == false)//gridMap[tmp_gridKey].isDrawn == false)
        {

            std::cout<<"Checking adjacent cells of "<<ref_gridId<<std::endl;
            std::cout<<"Obstacles check at "<<tmp_gridKey<<" is clear!\n";

            if (gridExists(tmp_gridKey) == true)
            {
                std::cout<<tmp_gridKey<<" is within the gridmap, so it is safe to add to drawing list.";
               // gridMap[tmp_gridKey].isDrawn = true;
                gridDrawList.push_back(&gridMap[tmp_gridKey]);
            }
            else if (gridExists(tmp_gridKey) == false)
            {
                std::cout<<"Error: "<<tmp_gridKey<<" was not found in the initialized gridMap";
            }
            std::cout<<std::endl<<std::endl;
        }

    }
    --ref_moves;
    if (ref_moves > 0)
    {
        tmp_gridKey = formGridId(tmp_gridPosition.x, tmp_gridPosition.y - 1);
        showPossibleGridMoves(tmp_gridKey, ref_moves);

        tmp_gridKey = formGridId(tmp_gridPosition.x, tmp_gridPosition.y + 1);
        showPossibleGridMoves(tmp_gridKey, ref_moves);

        tmp_gridKey = formGridId(tmp_gridPosition.x + 1, tmp_gridPosition.y);
        showPossibleGridMoves(tmp_gridKey, ref_moves);

        tmp_gridKey = formGridId(tmp_gridPosition.x - 1, tmp_gridPosition.y);
        showPossibleGridMoves(tmp_gridKey, ref_moves);
    }

}

This sorts of works...

(click to show/hide)

But not perfectly.

(click to show/hide)

Actually it doesn't work at all.

(click to show/hide)

Inconsistent too.

(click to show/hide)

Is there something wrong with my underlying code logic or am I making some major mistakes in coding? Or both? I feel like I have difficulties with trying to come up with the a working algorithm  Is there something very obvious that I am missing?

[sinelin]

I've got it solved now using recursion. Thanks guys