I picked up the A* algorithm from TANSTAFL''s iso book. It works great as far as finding the shortest path, but that usually doesnt look natural (this is a 2D Iso game, btw). Ive tried a few things, with some success, and am looking for more. Im sure this stuff has been talked about before, but One of the problems is the "zig zag" that happens because it costs the same to move diagonal as it does left/right/up/down. So if the end is 4 squares to the left, instead of moving just left, it may move up-left then down-left, down-left, up-left to get to the destination. So what I did first was instead of testing random directions when finding the next step, was first test the tile that is in the same direction as the unit is going. This elimates the zig zag when moving in a straight line completey. I also make it check in the directioon of the target (or rather the real start) for its first "move". This will set it on a straight path from the start if it is possible. The last thing I am thinking of doing is check at each step if the current position is lined up directly with the target. If it is, it should keep moving the the straight line. I think this would help eliminate "zig zags". I dont know this probably wont make much sense because you arent looking at my code or what I am talking about. I''d just like to hear of ways of improving the A* path finding method. Im not looking for anything complicated. I know you can accomplish a lot by using trees and other complicated things. Im just looking for little tricks to keep my units on somewhat natural paths. ratman --------------- Ratfest.org

A simple way of avoiding unecessary zig-zagging is to make diagonal moves cost more (they are infact longer than horizontal/vertical moves by a factor of sqrt(PI), which is almost equal to 1.4142).
So if a vertical or horizontal move costs 4 then a diagonal should cost 6, (avoiding floating point math here, you get the point).

Also look at this.

Edited by - Dactylos on June 15, 2001 3:50:40 PM

Your idea sounds good to me. I had noticed the same problem, Civ: CTP 1 and 2 both have that problem also.

I think when you have your unit pick which square to move to next (assuming there are 8 choices) you should have it start by looking at the square that points to the target and repeat until you get there.

Another possible way to do it is if you are looking at the 8 possible options in a clockwise analysis you can start by looking at the left-most of the 3 squares that are closest to your target.

Like this: Start w/ square 5 then go clockwise to go to T1, to go to T2 start with square 2
T1 = target1
T2 = target2
U = unit

-----------------812-----------------T2
-----------------7U3
-----------------654

T1

I think this will at least point the unit in the right direction and once the unit gets lined up straight w/ the target you can switch to using mode 1 which should take you straight to it.

Hopefully you can understand the way I explained mode 2, if not feel free to email me.

Rich



If it weren't for my horse, I would never have spent that year in college.


Edited by - Thellan on June 15, 2001 4:17:48 PM

'My' version is still simpler
You don't have to do any special cases. You always have costs for moving when using the A* algorithm and with the approach I outlined above you don't have to do any special cases, simply let different directions have different costs. i.e. all vertical and horizontal moves cost a specific amount, say X. Then diagonal movement would cost X*sqrt(PI) ~= 1.5*X

So if a unit has to move two squares to the right, then it will favor a straight path (at a cost of 2*X) instead of one moving up-right and then down-right (which would cost 2*X*sqrt(PI) ~= 3*X)

If you don't understand what I mean I can elaborate, or you can read (almost) any A* tutorial/description. Most of them I've seen do it this way . I'm sure there are some good ones in the Resources section of this site.

Edited by - Dactylos on June 15, 2001 4:33:22 PM

If, for some reason, moving diagonal needs to be the same cost as moving horizontally or vertically (example: king moving in chess, perhaps), make horizontal and vertical moves cost 1 and diagonal moves cost 1.00000001. This way, given 2 virtually identical paths, it''ll choose the one with fewer diagonals, because the path with the diagonals might cost 9.00000009 vs a score of 9 for all horizontal/verticals.

The number you choose for your diagonals is arbitrary, but it needs to be more than the horizontal/vertical cost, but not by so much that it will ever add up to enough to distort the path.

quote:

---

A simple way of avoiding unecessary zig-zagging is to make diagonal moves cost more (they are infact longer than horizontal/vertical moves by a factor of sqrt(PI), which is almost equal to 1.4142).

---

sqrt(PI)??? Don''t you mean sqrt(2)? sqrt(2) = 1.4142...

/MindWipe



"If it doesn''t fit, force it; if it breaks, it needed replacement anyway."