5 replies to this topic

[korinkoj1]

Hey guys, I'm a bit new to GML but have pretty good knowledge in both C++ and Java. I've been interested in making a simple Player vs CPU game that involves a frog pond setting.

The objective of the game is to stop the frog from reaching the outside area of the pond, the beach, by sinking lily pads around it. The frog begins in the middle lily pad and is surrounded by an offset grid (probably 9x9) of lily pads to jump on. The game would be turn by turn, first you click a lily pad, it sinks, and the frog must then recompute the shortest path to the shore, jump ONE lily pad, and wait for the player to again select a lily pad to sink, and so on.

X X X X X X X X X
X X X X X X X X X
X X X X X X X X X
X X X X X X X X X
X X X X O X X X X
X X X X X X X X X
X X X X X X X X X
X X X X X X X X X
X X X X X X X X X

I'm just looking for some guidance on how I can program the frog to compute the shortest path to the shoreline based upon the existing lily pads. I've heard of Dijkstra's alrogrithm and looked at the code but I'm having trouble relating network protocols to my game. I'm not looking for any exact answers or anything like that, just some simple guidance on how I can get started on this problem.

Thanks!

Edited by korinkoj1, 24 October 2011 - 11:43 PM.

[xshortguy]

There is a built-in path-finding algorithm in Game Maker [Standard and above, not Lite] that is essentially the A* (A-star) algorithm. If you want a pre-developed device, here's your answer. [Look up the mp_grid functions.]

The typical idea of the A* algorithm is that we use a heuristic function to estimate the distance needed to reach a given goal node, and then choose our next move based on that principle.

For example:

PRE

XXXXX

XXOXX

XXXXX

XGXXX

G here is the goal node.

For a heuristic, I can use anything to measure distance. In this case, I'll use the manhattan metric, which counts the total number of horizontal and vertical spaces to reach the goal node.

If we look around the starting place, the heuristic looks like the following:

PRE

XX4XX

X234X

XX2XX

XGXXX

I then will choose to move left or right to reach the given goal node.

This is a primitive description of how one step of the A* algorithm works, albeit a few missing details [such as keeping track of tiles I've already been in, etc]. If you continue this process through each step, you'll continue until you reach the goal node.

I'd also advise you to check out the first unit of the ongoing AI-class here:
www.ai-class.com

They have a good description of how the algorithm works.

[tangibleLime]

A-star is a "best-first search" algorithm to find the optimal path from an initial node to a goal node. By "optimal path", we can also say "least cost".

Say our path-cost function is and our heuristic function is -

Greedy best-first search uses the evaluation function: . It only looks at the heuristic value and chooses which node to traverse to based only on that.

Uniform-cost search uses the evaluation function: . It looks at the total path cost of each node before traversing to one. If at some point it finds a duplicate node with a lower path cost, it will swap it out for the more efficient one and will therefore return an optimal path.

A-Star (A*) combines the path cost and the heuristic by using the function:

Any of these three will work fine - it just comes down to efficiency. Heuristics dramatically increase efficiency, but greedy best-first search often fails at producing an optimal path. Therefore, I would suggest using A-Star.

EDIT: One thing to note about heuristics: they must be admissible. That is, they do not overestimate. Manhattan distance (mentioned in the post above) works well. Another common (but extremely less efficient) is the Hamming distance. Both are documented very well all over the Internet.

[korinkoj1]

Very good information, I will definitely take a look right now.

As for the goal node, I presume it would be relatively simple to calculate which of the outside nodes is closest to the NPC using some functionality of the algorithm and to set that node as the goal node?

Then I'm faced with the problem of how the NPC will decide which goal node to move towards first in the beginning of the game. Using the above grid layout, the NPC will have a lot of choices as to where to move first. Could I make the first goal node random?

Edited by korinkoj1, 25 October 2011 - 02:45 AM.

[tangibleLime]

I assume your goal nodes are all of the nodes on the outside of the "pond".

You could just use the Manhattan distance heuristic right at the start for each of the goal nodes, and see which returns the lowest value (i.e. it is the closest). If a few are tied for first, choose randomly between them.

Remember, for Manhattan distance, we want the distance the "frog" has to travel using only vertical and horizontal moves.

EDIT: Just for completeness: In your case, the Manhattan distance heuristic for finding that initial goal node would be...



Where (x1,y1) is the frog position and (x2,y2) is the position of the current goal node that is being evaluated.

[korinkoj1]

Lime, that makes perfect sense. I'm going to start the reading from the above posts and will begin programming tonight. I'll definitely return here for any questions.

Thank you both for your help, it was exactly what I needed.