search

famw / SpelunkBots

An API that allows for AI bots to be written in the original 2009 version of Spelunky.
http://spelunkbots.com
1 stars 0 forks source link

Improve function to calculate fitness #4

Closed wmartins closed 8 years ago

wmartins commented 8 years ago

As discussed before, we need to improve the fitness calculation. The following picture explain the ideas to improve it:

0

martinduartemore commented 8 years ago

After discussing with Meneguzzi, we agreed that a good way to test the bot's fitness is to take into consideration two factors: time taken and distance traveled. In order to combine the usage of two independent parameters in the fitness function, we need to standardize (or normalize) the parameters' value range. NEAT does not allow negative fitness values, therefore we chose to normalize the values using the range [0,1].

Time

SpelunkBots uses an user-specified parameter to control the maximum time a bot can take to complete a level. It also allows us to check how much time has passed since the beginning of a test. The formula used to calculate how much time a bot has taken to complete a map is the following:

T = (Tmax - Te) / Tmax

where Tmax is equal to the maximum test time and Te is the actual elapsed time.

If the bot remains idle for too long, we penalize it via: T = 0

Distance

The bot does not (and should not) know the exact location of the exit, so calculating the distance parameter is a little more trickier. Since we don't know how close we actually are to finishing the map, we need to come up with a generalization that works with all maps. Since a cave level's map is always the same size (40 by 32), we know that the longest possible distance between the entrance and the exit occurs when the entrance is located at (1,1) and the exit is located at (40,32).

If we store the bot's initial location we can roughly know the distance the bot travelled if we calculate the manhattan distance between two points and compare that to the longest possible manhattan distance the bot could ever travel in a map. The formula used to calculate the distance traveled is the following:

D = Dt / Dmax

where Dt is equal to the manhattan distance between the entrance and the bot's last location and Dmax is the longest possible manhattan distance from an entrance to an exit.

If the bot is able to travel from the entrance to the exit, we reward the bot by saying that D = Dmax.

Combining Parameters

We can combine these parameters in many ways, like using the average, mininum value, maximum value or using weights. We are still experimenting with combining the parameters.