Goal-based vector field path-finding in godot2d.

WildWestPony

Hi guys Im using gdscript and trying to implement goal based path finding in 2D. In order to do so i need to create a heat map of distances from a point(left click mouse position) and from that, generate a vector field to tell a sprite or other what direction to move to get to the target.

Currently im generating a set of nodes arranged as a grid and getting them to check for changes in neighboring nodes. My plan was to use that and store in each a int var for distance and vector2d for direction. This seems to be quite cumbersome. The calculations aren't hard but the method im using isn't very streamlined. If only I could code it with MatLab and it'd be alg lol

Can anyone suggest an approach i could take t generate a vector field on each mouse click.

Heres an example of the sort of movement im looking for expect for a single particle: https://gamedevelopment.tutsplus.com/tutorials/understanding-goal-based-vector-field-pathfinding--gamedev-9007

SIsilicon28

It already sounds like you have the solution down. I'm not sure what you're asking for.

When you say nodes, are you using literal Godot nodes, or just a data structure in GDscript that you made?

WildWestPony

Nodes lol I just want dot get the math working first. With a structure can I get them to interact with adjacent cells of data? Like if an adjacent cell is not null I want this cell to be x(celladj) - 1 And if this cell corresponds to a wall in game I want it to act differently.

SIsilicon28

Well personally, I would've used a Dictionary to store the data. That way it is easier to retrieve the vectors and other data. I could go into more detail later.

WildWestPony

Yes I was thinking originally to use a dictionary. But I'd have to go cell by cell. Like on mouse click I update that cell, then each adjacent cell. Then each adjacent cell to those and so on. Where as id like each cell to sort if manage themselves.

Unless there's a method to do that in a dictionary? I think for example you could make a func in Matlab and use it on a cell array but use it to simultaneously work on each cell

SIsilicon28

A dictionary can have any kind of key to access data, including vector2. You can make a while loop that goes through each "node" that needs updating (boundary conditions required or infinite loop).

Start with where the mouse click happen. Convert the mouse position to grid space, and add a "node" to the dictionary with those grid space coordinates as the key. The node will start with the number 0. Also add it to a temporary array of node coordinates.
Attempt to add nodes to the top, bottom, left and right of this node. If the coord you're attempting to insert is beyond boundary, is a wall, or another node, then don't add anything there. Give those new nodes the previous node incremented, and add them to the dictionary and temporary array. Remove that previous node from the array however.
Repeat step 2 until the temporary array is totally void of coordinates. The dictionary should now be filled with the distance to the mouse click.

SIsilicon28

I know it must be really difficult to understand all that, so I'm gonna make a demo script for ya. ;)

SIsilicon28

Here ya go! https://github.com/SIsilicon/Path-Vector-Field-Godot-Demo

I may have put in more than required. If there's something you don't understand, let me know. Bare in mind I only made this in 2 hours.

WildWestPony

Thank you! This will clear it all up for me and help me figure out how to implement. i considered looping through an array, but figured it (the program)would take a loooong time depending on how many blocks it has to loop through. Im used to working with programmes like matlab so was really unsure of how to implement with godot

again, thank you so much!!