Flex and polygonal.de graph classes in pathfinding?
I am wondering if someone have done this already, to send 开发者_运维知识库me into right direction..
- The issue is as follow : I have a 2 dimensional array, on which i hold integer numbers, if the number is 0 - the item shall not be included into the graph, if it is 1 - it must be included. The result graph shall be used for patfinding ( the shortest path ) to some element.
- how to turn this 2 dimensional array into the graph ? ( with polygona.de classes if possible ),
I am currently trying with Polygonal.de classes. any suggestions and points into the right direction is more than appreciated.
This is the 2 dimensional structure. The red cells is prohibited to walk on, and there must be found optimal path from "start" to the "end". But 1st things 1st - i need to turn this 2 dimensional structure into a graph now :|
The way I see it, your 2D array is already a graph. A node of the graph is represented by a pair (i, j)
and may have neighbor nodes such as (i + 1, j)
, (i, j + 1)
, etc. You can write a utility function for your array that hides these low-level neighbor definitions and skips the cells that are occupied.
The de.polygonal.ds API for the Graph data structure contains this example for the construction of a graph:
var graph = new de.polygonal.ds.Graph<String>();
var a = graph.addNode("a");
var b = graph.addNode("b");
var c = graph.addNode("c");
graph.addSingleArc(a, b, 1.0);
graph.addSingleArc(b, a, 1.0);
graph.addMutualArc(a, c, 1.0);
Adjust the example to construct a 2D array that contains a node for each free (i, j)
of the original 2D array. Then traverse the 2D array of nodes and call addMutualArc()
to connect adjacent nodes.
精彩评论