Friday, December 1, 2017

Grid Movement and Pathfinding

Hi everyone,
I'm not sure how interesting the following would be but I thought you'll might like to hear a bit about the more technical side of the new game's development.

Tactical/Strategy RPGs games are among the most difficult types of games to make(for making the engine from scratch), one of the main reasons for this is the complexity.

For this game's battle system, the gameplay happens mainly in 2 different view modes: top-down and side-scrolling.  The top-down(overmap) view is similar to tactical rpgs such as fire emblem where you select each character and move them. The side-scrolling(combat) view is more like platforming-style fighting with the player controlling the character directly with the keyboard or gamepad.  As for the basic flow of the game, you move characters in top-down view and enter direct combat in the side-scrolling view.  But for now, I'll focus this post on the top-down(overmap) interactions.

The overmaps in this game uses a 64x64 pixel grid based movement system similar to games such as fire emblem.  Original I made it using a much smaller 32x32 pixel grid, but I wanted to make the characters bigger(which is also easier on path-finding) so I decided to go with 64x64.

The test-build image above shows the mother and daughter(as well as other things) on the grid-based overmap.  The blue squares on the map represents the daughter's movement range(think of each blue square as a grid-step, here you can see the daugther's movement is set to 5 grid-steps).  The grid system and basic movement on it is pretty easy for me to make, but what makes things more difficult is the path-finding, specific for the blue-squares here.

If you're wondering what path-finding is, it's basically finding the shortest route to get from one point to another while avoiding obstacles.
Without considering obstacles, the blue squares' positions can be calculated pretty easily.
For example, the daughter's movement is set to 5 grid-spaces, which means she can move 5 spaces away from where she is standing.  This is represented by the blue-squares.

But you might be wondering how does the game know where to draw each blue square?
First look at them vertically, they are drawn here in columns.  Specifically, the way the number of blue squares per column is calculated and drawn is like this: Start 5 grid-spaces to the left(5 is the daughter's movement) and draw 1 square, then grown 1 up and 1 down as it moves to the right until it reaches the daughters position(now 11 blue-squares), then reverse the process to make the right side(ending with 1 again on the right side).  And if there is a collision, the blue square isn't drawn at that location(in this example the big red box is the collision object).

This may seem like enough to make a good range of movement at first.  However, when you move the daughter next to the red-collision object, there will be directions she cannot walk 5 spaces due to collisions with the red-collision object(but the blue squares won't account for this(see above image).  note: the daughter cannot walk through the red-collision object, she must go around it.).

One of the ways to fix this is to use path-finding on each blue-square.  For this I mean that each square will see if a path can be made from it's position to the daughter character's.  If a path 5 grid-spaces long or less is found, the blue-square is drawn on-screen, otherwise it isn't.  With every blue-square using path-finding it might sound like that would be slow, but it all happens instantly due to factors such as the size of the grid, the distance from the daughter and the path-finding algorithm used.

After path-finding is applied(and an attack range of  3 is added and represented by red squares), the movement looks like this.  Now it correctly shows that she can only walk 5 spaces in each direction while also accounting for the collision object next to her.  This is basically how the movement/attack grid is calculated and drawn in the game now.

If your wondering about the long-skinny-red objects, those represent enemies, if she move in range and chooses to attack, the grid will correctly show which enemies can be attacked(see above image).  The game also builds a menu based on where your character has moved and what is able she do.  For example, in the image above, the 2 menu options right now are "Attack" since she's next to 3 enemies and "Wait"(which ends her action).

If you were to choose to "Attack" one of the enemies, it would take you to the side-scroll view map like this for combat. (The image above shows 2 instances of the mother moving, jumping and attacking for test purposes).

I don't know if you find this post interesting or confusing but I thought I would try to talk about this game's development more.  Right now, the game can cycle through both view modes.
I'm still not ready to talk too much about the story just yet, but I will reveal much more in the not to distance future, as well as tell you guys more about the game-play.

Also, you can still vote on the last poll here:

um, that's all for now,
see you guys later. ^^

No comments:

Post a Comment