My first game progress and BFS (Breadth-First Search)

Hello,

I am working on my first game, and I want to share my progress. I thought it would be an easy first project, but it turned out to be a real headache :melting_face:

First, I really love isometric games, so I used 2D diamond-shaped tiles inspired by Into the Breach. While it was easy to set up the map, that was the only easy part. Soon I realized that pixel coordinates do not work very well on this kind of grid. To make movement smooth, I had to match the exact pixels of the tile, and it was really hard to do with an isometric grid. The more I moved, the more my player went off the grid. So I created a virtual layout - I added Tile variables GridX and GridY and set them manually for each Tile instance:

(0,0) (1,0) (2,0) (3,0) (4,0) (5,0) (6,0) (7,0)
(0,1) (1,1) (2,1) (3,1) (4,1) (5,1) (6,1) (7,1)
(0,2) (1,2) (2,2) (3,2) (4,2) (5,2) (6,2) (7,2)
(0,3) (1,3) (2,3) (3,3) (4,3) (5,3) (6,3) (7,3)
(0,4) (1,4) (2,4) (3,4) (4,4) (5,4) (6,4) (7,4)
(0,5) (1,5) (2,5) (3,5) (4,5) (5,5) (6,5) (7,5)
(0,6) (1,6) (2,6) (3,6) (4,6) (5,6) (6,6) (7,6)
(0,7) (1,7) (2,7) (3,7) (4,7) (5,7) (6,7) (7,7)

Then the remaining problem was pathfinding. As expected, the GDevelop pathfinding behavior did not work with my virtual layout, so I had to make something similar and this is where I found about breadth-first search. TLDR I added two variables to the Tile: Walkable - if there is an obstacle on the tile it changes to 0, otherwise it is 1, and Distance which is 999 by default. When I select a Player, it creates an invisible Object1 in all 4 directions unless the tile is not walkable, and changes the Tile variable Distance to 1. Then the Object1 creates invisible Object2 in all 4 directions etc. The process repeats until Object7.

Then I added a variable MovePoints to the Player. If Distance is less than or equal to the Player’s MovePoints, that tile is highlighted and the Player can move there. When the Player moves or cancels the movement phase, the invisible objects are deleted. In the GIF image I am increasing MovePoints by 1 to show how the highlight bypasses obstacles.

ezgif.com-animated-gif-maker (1)

This is by no means a perfect solution. I hope GDevelop will be forgiving of my clumsy events :melting_face: But I am happy that something worked today.

3 Likes

Hey, welcome to the community! We are so happy to have you here!

That project looks super cool!

Make sure to post more when you figure more things out, I’d love to hear about them! :smile:

1 Like

Thank you so much :blush::pray:

Yes i am glad to good luck this community is very inclucive.

1 Like