Basic A* pathfinding algorithm question

[K29]

Just looking for some advice here.(This is the first time I'm doing anything like this so please bare with me)

I have been given a project where we have a game and 4 agents (the other 3 agents are other computer science students) The idea is to program a good AI that can beat theirs.

I am going above and beyond what was required and researched a basic A* pathfinding algorithm with manhattan heuristic. I am currently coding this in java for the game. The game is a 2d grid with worms as agents. each worm takes up multiple squares.

I am worried that it will be problematic though. The game engine allows for 50 milliseconds to respond with a "move" for your agent, (if you don't respond in time it moves it in whatever direction you are facing which is NOT good) I am told that 50 microseconds is a long time in computer terminology. But A* looks expensive. The board is 50 by 70 for the game and there are 4 "obstacles" (my worm and my opponents worms). There are 3 degrees of movement for a move (straight, left, right, but not back on yourself because the agent is a worm)

Do you think I am wasting my time on this or will basic A* finish in time(50 ms)?(apparently the server which our agents will be tested on has a quad core i5 I think) The worst case on a 50X70 board of squares I'm scared may take too long, but as I said the only obstacles are yourself and other 3 worms which can each take up a maximum of 59 squares each in the worst case.

 

[Hurkyl]

Given enough real-life time, you should try a lot of different AI's for your worm.

I've never actually looked at the algorithm, but I was under the impression that the A* algorithm allowed you to tune its running time -- that there was a parameter you could tweak that controls how much or how little effort you put into path-finding.


Are you allowed to save data from one call of your function to the next? Maybe you can speed things up even further by remembering the results of previous calculation.

 

[K29]

A* looks at different nodes adjacent to your agent or previous nodes the path you are constructing and associates a heuristic cost to each node by choosing a simple path to the target(ignoring obstacles) and a "past" cost based on the cost of nodes to get to the current node you are examining in your path. The costly part of the algorithm is comparing a nodes' final cost to a large amount of other nodes' costs on the board and this has to be repeated multiple times until you have a path to your destination.

Great idea! I could remember the current node with smallest cost and I won't have to cycle through all the nodes every time, just the new ones that are added will need to be checked. Remembering a solution path from the previous timestep of the game could also be handy, but then I need to read and write a line from a textfile. Is a harddisk read and write expensive? (Sorry, I'm just not sure about relatve speed of such things, especially since I'm not using the computer that it will be tested on in the end)

 

[Hurkyl]

Accessing disk is slow (and often unpredictable); you don't want to do that. You just want to put the results in some object that can be accessed by your function.

 

[DeeNos]

As a scientist, my advice would be to first test the basic A* algorithm on a smaller scale, such as a 10x10 grid, to see how long it takes to find a path. This will give you an idea of the algorithm's efficiency and whether it can be completed within the 50 millisecond time limit.

If the algorithm does not finish in time, you can try optimizing it by implementing techniques such as pruning or using a different heuristic. You can also consider parallelizing the algorithm to take advantage of the quad core i5 processor.

It's important to also consider the complexity of the game and the behavior of the other agents. If the other agents are not using efficient pathfinding algorithms, then your basic A* algorithm may still have a chance to outperform them.

Overall, it's always good to go above and beyond in a project, but also be mindful of the constraints and limitations. Keep testing and optimizing your algorithm to find the best solution within the given time frame. Good luck!