I have an open space strategy game where “pieces” can move in any direction a limited distance based on their class.
On the "board’ there are various barriers that the pieces need to move around.
I am trying to implement the logic for the computer player and having problems with one part and was wondering if anyone had hit this before:
I started by using an A* algorithm to determine shortest path. I did this by creating a cell size and then just splitting space into cells so while there are no set board spaces it can use cells to speed up decisions (instead of pixels).
So that went great and the A* returns a series of moves left,right,up,down and distance.
The problem is:
1, The piece will move from point A to point B along the path, usually not the entire distance in one move
2. The piece can only go in a straight line (but 360 degrees) on a single turn but the A* path is up,down,left,right so unless I move very short distances I can’t figure out the most efficient way to move.
CONSIDER THIS EXAMPLE WHERE X is a barrier and S is start and E is end
[S]XXXXX [E] X
XXX X
XXXXXXXXXXX
The path would be DOWN 2, RIGHT 7, UP 2
But because I can go in a straight line I could go DOWN 2, RIGHT 3 on this turn (diagonal)
So my question is how do I figure that out in a generic/efficient way?
I was thinking of traveling the path produced by A* and drawing a line back to the start and making sure at each cell there is no intersection with a barrier but this seems like it might be too slow and also I’m not sure if that would provide optimal results
I suppose I’m looking for two things, using A* was about determining shortest path but perhaps another technique could provide shortest number of straight line moves in 360 degrees?
[import]uid: 111413 topic_id: 28208 reply_id: 328208[/import]