Jump to content

  • Log In with Google      Sign In   
  • Create Account


#Actualplainoldcj

Posted 22 April 2013 - 05:05 AM

I would approach this problem the following way:

 

Build a graph G = (V, E) from your mesh, where the nodes V are the movable tiles (ie. faces) of your mesh

and the edges connect adjacent nodes.

Common representations for graphs are adjacency lists and adjacency matrices.

In this case you could even use adjacency arrays, since for each node the number of adjacent nodes is constant.

Each node should have a reference to the face it represents or at least a position coordinate.

 

Finding a shortest path on graphs is a solved problem. Use your favorite algorithm for this, maybe A* or the

general dijkstra. Dont store shortest paths, recompute them. I doubt it will be a bottleneck.

 

Sidenote: as mentioned above, dont introduce special cases with null-pointers to handle impassable tiles.

Just use high costs. Speaking of costs: dont forget to test different measurements of distance.

normal l2-norm might not be the best on a spherical surface.


#1plainoldcj

Posted 22 April 2013 - 04:59 AM

I would approach this problem the following way:

 

Build a graph G = (V, E) from your mesh, where the nodes V are the movable tiles (ie. faces) of your mesh

and the edges connect adjacent nodes.

Common representations for graphs are adjacency lists and adjacency matrices.

In this case you could even use adjacency arrays, since for each node the number of adjacent nodes is constant.

Each node should have a reference to the face it represents or at least a position coordinate.

 

Finding a shortest path on graphs is a solved problem. Use your favorite algorithm for this, maybe A* or the

general dijkstra. Dont store shortest paths, recompute them. I doubt it will be a bottleneck.

 

Sidenote: as mentioned above, dont introduce special cases with null-pointers to handle impassable tiles.

Just use high costs. Speaking of costs: dont try to test different measurements of distance.

normal l2-norm might not be the best on a spherical surface.


PARTNERS