![]() ![]() ![]() This algorithm finds all possible paths between all nodes and leaves each node a list of nodes one should travel to if they are to reach a specific destination node. The algorithm I selected for shortest path calculation is the Floyd-Warshall algorithm. For my fellow CS nerds, it runs in order n-cubed time (for every n nodes, we perform n×n×n steps). If you’d like to view the source code of each script individually, here are some pastebin links: If you’d like to view my implementation of graph, node and edge objects, you can download an rbxmx file here. The weights of the edges are the euclidean distance between the nodes. ![]() At runtime, I have the game convert my Parts and ObjectValues into nodes and edges in a graph. Now I have a representation of my map’s network of navigable areas. ![]() However, I am working with a sparse graph, which means the 100+ nodes only connect to a select few (2-6) other nodes near to them. This is one of the two main ways to represent a graph in memory the other method is to store an adjacency matrix of size n-by- n, where n is the number of nodes in a graph. This is essentially building an adjacency list, where each node contains a list of adjacent nodes. Inside each of these Parts, I added ObjectValues whose Values point to adjacent locations in which a minion should be able to travel between. Pink nodes represent a path yellow represents a junction. I placed parts in Roblox Studio on my map to quickly identify such locations: On my map, there are places that I know a minion can be, and I know which of those places can be accessed from nearby places. Graphs are about relationships between objects. In this article, I’ll outline how I applied graph theory (described in the first article) to solve my problem. In the previous article, I described a problem I faced when developing a game with little dudes roaming around a pre-built map. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |