11-03-2004 06:43									#1
	A* and artificial intelligence. Support Apolyton

I wrote a small article on ai and pathfinding in relation to strategy games. It is mostly about the ideas I have and methods I put into use to increase the 'intelligence' of artificial players.

The method to fix the anoying killzones and the method to let units use roads alone is described.

http://www.hardcorecoder.com/articl...athfinding.html

	13-03-2004 00:39									#2
	Support Apolyton buy from Amazon

Looks like you added costs as (terrain + road cost + army there cost).
One problem I found in Clash is that computing the cost of units standing in the path is problematic. Units you'd have to fight along the way are a problem for two reasons: -they slow you down (thus a cost in terms of speed), -they can kill or weaken your army. The second term depends on which unit you are moving. For instance, moving a huge army means you can safely ignore a single unit, but sending a scout is not a good idea. Therefore, the path chosen depends on the unit. This leads to several problems:
-How long do you keep danger zone values? For as long as you have information on the region? For a heuristically determined amount of time?
-What do you do if you realize you are entering a danger zone? You probably cancel the order/path, but you may want to ask for reinforcements or chose another path/target. If you ask for reinforcements, it's probably not a good idea to sit like a duck waiting for the opponent to attack you...

One small thing I found useful in A*: A* doesn't produce the same paths from A to B and from B to A. You can have paths like this:
A----\
\     \
\-----B
So I forced computations (A,B) and (B,A) to always pick the same path (arbitrarily choose one path as the starting point) in order to allow units moving one towards the other to be able to meet rather than go around endlessly in circles.

	13-03-2004 01:43									#3
	Suffering from ads?

quote: -How long do you keep danger zone values? For as long as you have information on the region? For a heuristically determined amount of time?

I think once a scout unit explored the terrain it can be considered safe. Depending on the resources scouts can be send at a slower or faster rate. Having watchtowers in a region might also be usefull to signal if there is a enemy presence nearby.

quote: -What do you do if you realize you are entering a danger zone? You probably cancel the order/path, but you may want to ask for reinforcements or chose another path/target. If you ask for reinforcements, it's probably not a good idea to sit like a duck waiting for the opponent to attack you...

Imo a players own terrain can be seen as safe. The romans build defences on their borders and knew nothing came in. Anything moving out could expect anything so were 'prepared' Scouts can help in this.

I think once a army has moved out of friendly terrain into a unsafe territory and finds itself unprepared to match the counter forces there it depends on strategic evaluation what it will do.

If a players own terrain is invaded then logically regular units should be recalled until the area is secured. They would be destroyed otherwise.

quote: One small thing I found useful in A*: A* doesn't produce the same paths from A to B and from B to A. You can have paths like this: A----\ \ \ \-----B So I forced computations (A,B) and (B,A) to always pick the same path (arbitrarily choose one path as the starting point) in order to allow units moving one towards the other to be able to meet rather than go around endlessly in circles.

When I started using a* I had a lot of problems with it, and still do sometimes. Its a funny little algorithm but very powerfull.