Fata1Attack

Hi all,

I'm creating a game and I nead to know the shortest path from point A to point B. I started programming it, but I still get a lot of problems that I can't get rid of.
Here is an example of a situation I mean:

A: Starting point
B: Location to end at
X: Place where you can't walk at
1: The path that should be chosen.
(You can not move diagonaly.)

B

1

1

1

X

X

X

1

X

1

1

X

1

X

A

1

1

What is the best way to program any situation, so you can retrieve the best and shortest path. I started with some basics and etcetera..But what must I exactly do Using random Using technology



Re: Visual C# General Short path

Flip

The short answer is you will need to look at Graph Thoery to find the shortest path. Or you could do a search on adjacent nodes. But I would suggest looking into the Graph Theory thing to solve your problem exactly but yet generically enough to apply to other areas of your game.

Good luck.





Re: Visual C# General Short path

John.Doe

Well, first of all you need a data representation of your problem in this case a graph would be suitable that can be represented as an adjacency matrix. In your case you got 20 nodes in your graph (the fields of your map), so build a two dimensional array 20 x 20, where every index represents a node in your graph. Initialize the array so that wherever you can travel from one node to another one there is 1 else 0.

e.g.
A B C D
A 0 1 0 1
B 1 0 1 0
C 0 1 0 0
D 1 0 0 0
(not a representation of your problem obviously, so A and B here are not A and B as in your map - this is just an example)

Would mean, e.g. that from node A you can travel to B and D, or from C you can travel to B. The graph will be usually symmetrical on the diagonal if the graph is not directed, i.e. you there are scenarios where you can e.g. travel from A to B but not from B to A.

And now you can either use a kind of brute force method to find the shortest path by just starting from one node and recursively trying out all possible solutions (maybe good for learning, but impractical). Or you can search for e.g. the Dijkstra algorithm and apply that one to your graph and it will give you the shortest path from A to B ;)