1
\$\begingroup\$

So I've implemented pathfinding to my game which works well with a tile based map. All tiles have an x & y integer coordinate for example the tile on the top left would be 0,0 the adjecent tiles would we 0,1; 1,0 and 1,1. My pathfinding returns a path based on these coordinates.

My game however is using float coordinates. So that an entity is basically able to stand on or between two tiles at the same time. For that the tile coordinates are multiplied by 32 (the size of one tile). That means the first tile would be 32,32 and the adjecent tiles 64,32; 32,64; 64,64

My approach was to get a target X and Y from my pathfinding to calculate the next step and multiply it by 32. So if the entity is supposed to move to the top left for example the targetX and Y would be 1*32, 1*32.

After the targetX & targetY is set i'll increase or decrease the coordination of moving entity by its movementspeed, when it's reached its targetX & targetY i'll get the next step and to the same until no steps are left.

However I'm encountering various problems because it's not really possible to set an entity to a certain field because its possible to stand on two tiles at the same time and entities only have float coordinates. Especially when an entity is supposed to move around a narrow corner its getting stuck because of the offset between the pathfinding and the float coordinates of the entity.

I hope my problem became more or less clear, how could I deal with that or how is dealt with that problematic in general? I'm glad about any advices.

Edit: No diagonal movement is intended.

\$\endgroup\$
  • 1
    \$\begingroup\$ Is your A* providing a set of way points at the centres of each of the titles. And does your A* permit diagonal movement (nothing wring with that but it's more complicated as you should only allow it when all 4 tiles that are passed through are empty) \$\endgroup\$ – Richard Tingle Aug 27 '17 at 12:51
  • \$\begingroup\$ Good Point: It does not permit diagonal movement. The set provided by A* of the points is on the top left of each tile, not the center. \$\endgroup\$ – LOLWTFasdasd asdad Aug 27 '17 at 12:52
  • 1
    \$\begingroup\$ That could indeed be causing the clipping the corner problem a +0.5 before multiplying by 32 may be all you need \$\endgroup\$ – Richard Tingle Aug 27 '17 at 12:54
3
\$\begingroup\$

A* is inherently an integer process, a tile is either travelled through or not. However your world is a floating point one; you can stand at 0.3,0.4 if you like. As such you need to convert from the A* output to a set of way points in your coordinate system. Personally I would make each tile of size 1 and allow floating point numbers. As such you would add 0.5,0.5 to each of the A* positions to get your waypoints; the centres of the tiles travelled. You appear to have chosen to make each tile 32 by 32. In this case you should multiply by 32 after adding 0.5 to each A* value to get the tile centres. If you have your waypoints at the top left of each tile as I believe you have you will inevitable clip the tile above and to the left of the character

\$\endgroup\$
  • \$\begingroup\$ Thanks for the hint, I'll try it out, hopefully I got you right. \$\endgroup\$ – LOLWTFasdasd asdad Aug 27 '17 at 14:34
0
\$\begingroup\$

This has to do with the pathfinding algorithm itself, not with the float coordinates. You'd encounter the same problem even if the tiles were integer based and the entities were larger than one tile in radius. What this has to do with the pathfinding algorithm is, when you check if a tile is valid to move to, you have to make sure the entity can stand there. Check all the surrounding tiles (in floats) and make sure the entity can stand there. If it can, then it'll be a valid path. Here's an example if the entity's radius was 3 units:

public boolean isValid(TileBasedMap map, int x, int y)
{
    if(x >= 3 && x < map.width - 3 && y >= 3 && y < map.height - 3)
    {
        for(int i = -3; i <= 3; i++)
        {
            for(int j = -3; j <= 3; j++)
            {
                if(!map.getTile(x + i, y + j).isEmpty())
                    return false;
            }
        }    
        return true;
    }
    else return false;
}

In summary, this applies to your problem because you convert the coordinates from 0-1 to 0-32 because of your floating point coordinates. This makes the entities much bigger than they actually are. They're now 32 units large (in theory) so you have to account for that in your pathfinding.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.