Legacy GM Making a graph/grid like node system[solved]

S

Sanil

Guest
Hello fellow game designers and programmers, I have (very)recently started to work on a breadth-first pathfinding algorithm and after some really long posts(here), I finally managed to get a grasp on how the algorithm would be programmed.... after working most of it out on paper I realized that a grid like system had to be made with each vertex(a point where any four given edges would meet) as a node........ but I've literally got no idea how to do it(mp_grid?) so if anyone knows anything about the topic please help me. I would really appreciate any small code or even a name of functions to do this would be good enough....Thanks in advance and oh, if you do visit the link above it's best to not read any of my code in it cause I've already deleted it from my little learning project....
 

kamiyasi

Member
You can create a grid for pathfinding using mp_grid and populate it with objects using mp_grid_add_instances, and set which tiles can't be crossed using the cell functions, mp_grid_add_cell(id, h, v); and mp_grid_add_rectangle(id, x1, y1, x2, y2);
 
S

Sanil

Guest
Thank you @kamiyasi for the reply I really appreciate it, I only have one query..... You said
You can create a grid for pathfinding using mp_grid
now as far as my knowledge goes, I don't think mp_grid functions can be used to create custom algorithms(I may be totally wrong) because there is no way that I can access any variables or anything and moreover this function is used mostly for using gamemaker's own pathfinding. So is there another way of doing this like with a custom made grid or anything or do I have to stick to mp_grid?

[Edit]- I just found about the function 'mp_grid_to_ds_grid', can that be used to access the variables and the data?
 
Last edited by a moderator:

NightFrost

Member
GML's mp grid functions only operate in the context of its own motion planning. You cannot influence it in any way, like altering costs between nodes (cost is always uniform across the grid) or creating a custom node set (it is always grid shaped). The only way is to build your own system from ground up, but since you understand how the algo works it is a matter of putting down the time to write it, and deciding how to present the graph with GML data structures.
 
S

Sanil

Guest
@NightFrost Yeah well grid creation is the only thing that I can't seem to figure out because I am unsure as to which functions to use for creating a grid but I feel that this might work as far as grid creation is concerned(or should I use mp_grid_to_ds_grid for creating a data structure)
Code:
Cells_wNum = room_width/32;
Cells_hNum = room_height/32;
or maybe I can store the coordinates directly into a ds_grid?
 

NightFrost

Member
When I created a flow field generation system, which admittedly is a different thing, I created my graph with ds_list. Each position in the list represented a node, and contained another ds_list that told what the neighbouring nodes were. Of course since my flow field was grid shaped I did not need to consider actual node positions, as it was a function of its list position (in a flow field of 20x20 nodes, list entry 20 is logically the first on the second line). Positions are not relevant to actually traversing the graph however.
 
S

Sanil

Guest
Hmm.. that's an interesting way to do this..... I'll b most probably be using this for creating my node system but I'll most probably use arrays cause any single node can be connected to only four neighboring nodes at a time and I feel that it is better to use arrays rather than data structures wherever it is possible but anyways thank you for replying, I'll be most probably be able to use it for the requirement.
[Edit]- Wait so how can a single list contain both the x, y positions of the nodes?
[edit edit]- alright never mind the above question after digging up some more info on ds_list, i realized that we don't require the x, y coordinates
 
Last edited by a moderator:

NightFrost

Member
In my case, the graph overlaid a grid, so each grid cell corresponded to a graph node. They found their node by doing x + y * width. This means for each impassable grid cell there is an unused spot in the ds list. It may go against someone's aesthetic sense to use a ds list inefficiently, but the fastest method to number the graph nodes is to make them correspond to ds list position. Any other method would require actually storing the node number, and then trying to find the correct ds list position when you have to get node #X. When you are in the middle of a loop that iterates through large number of nodes, speed is essential.
 
Top