Tag: algorithm

Quirk #3: Shorter, but is it?!

Quirk #3: Shorter, but is it?!

by Gus Martin ♥ 0 Leave a Comment

Hello folks!

In the process of today’s update, I came upon an interesting quirk when using grids.

I have finished implementing the hole creation in the new terrain, works like a treat. Now I’m in the process of processing the tiles in between the hole and the tee, so it can make calculations regarding base shot, par, actually distance etc.

Using A* to find the shortest path between the hole and the tee, leads to some interesting visuals:

astarlol

Above, the path traced by A* is marked with black spheres. The drawn red line shows the actual shortest path (a straight line) between the two points. When in a grid, the path marked by A* does signify the shortest path between two certain points in the grid. It can be set to ignore diagonal traversals, or to allow them (as is the case of Boss Golf).

Visually, though, it looks so quirky. To us, it’s clear to see that the shortest path is the line between the start and the finish. To the game, though, the shortest path ends up creating these doglegs all over the course.

That’s all! Almost done with the processing of the base shot, coupled with a lot of refactoring and reinforcement. Once it’s done, it’s demo time!

Stay tuned!

Quirk #1: Greed isn’t good

Quirk #1: Greed isn’t good

by Gus Martin ♥ 0 Leave a Comment

Inaugurating the Quirk category, is an interesting problem that appeared when trying to program the base shot function to avoid tiles where the next stroke would be blocked.

As it is now, the algorithm can be considered greedy; that is, it tends to find the local maximum instead of the global maximum. What does that mean?

The function to find the next best stroke focuses on mainly one factor: Distance covered by the stroke. So the function will always try to travel as far as possible with each stroke in order to minimize the Par score. However, in taking obstacles into account, sometimes the stroke with the furthest reach is not the best stroke! As we can see below:

Greedy1

There’s at least two or three tiles before the chosen one that could be used for a perfectly fine stroke, which would eliminate the danger of hitting either of the two trees in the middle. But since the algorithm is currently greedy, it’ll maximize locally, completely ignoring the global maximum. If we tweak the course further, like below, we can safely get rid of this issue:

But this is not good. Users would look at the course and go “What! There’s a perfectly fine play to be done over there! Dumb game!”. And we can’t have that!

So it’s time to smooth out the stroke calculation to look into the future for at least one or two moves, so that it can more accurately get rid of local maximums, and aim for the global.