Pathfinding Resources

Pathfinding Benchmarks

Grid-Based Path Planning Competition


AAAI 2020 Tutorial on Heuristic Search

AAMAS 2019 Tutorial on Heuristic Search

GDC 2018 talk on bidirectional search.

IJCAI 2018 Tutorial on Heuristic Search

Past Events

AAAI 2020 Student Activities

AAAI 2019 Student Activities

AAAI 2017 Job Fair

AAAI 2017 Workshop on what's next for AI in games

AAAI16 Student Activities

AAAI15 Student Activities

MAPF 2012 Workshop

AIIDE 2011

GIGA 2011

SoCS 2010

Snakebird - Anhinga - EPCG

In this project we are exploring how we can use exhausitive procedural content generation (EPCG) to help understand the consequences of design changes, as small design changes can have unexpected consequences. We are exploring this in the context of Snakebird, a game developed by Noumenon Games. We have developed our own version of the game which we call Anhinga.

The idea behind EPCG is to use computing power to explore all possible content, which then shifts the question to how to select the best content. Some example content that we have created for The Witness can be found here, and you can also read more about this work.

In Snakebird we aren't capable of generating all possible levels (there are too many and most are not interesting). But, we can analyze possible changes to a level. We hypothesize that human designers will not always recognize how small changes to a level may have a large impact in the solution space. Thus, we took all the levels in Snakebird and Snakebird Primer and asked the question: If you could make one change to the level to increase the solution length maximially, what change would you make?

Below are some of the results of levels where this analysis has been applied. These levels are not necessarily "better" than the original levels, but they highlight the unexpected impact of small changes in a level. We provide a selection of levels with large differences in solution length via small changes in the map. (Adding 1 or 2 new obstacles.) There are other levels with smaller changes in minimal solution length which still make the levels much harder for humans. It is also sometimes the case that some people only find the longer solutions induced by these changes and aren't aware than the shorter solutions were possible.

Notes: These are advanced levels which will likely only be solvable by those who have played the original game. If you don't want the challenge of solving the level, there is a solver that will show you the solution. But, if you've played the game, these levels will offer a new challenge!

We will be releasing an editor shortly which will allow you to load simple levels and explore modifications to them.

Original LevelSolution [length]New Level
(Click to Play)

Snakebird Primer Level 53

Solution [23]

Variant: +2 obstacles [50]

Snakebird Primer Level 65

Solution [29]

Variant: +2 obstacles [74]

Snakebird Primer Level 68

Solution [22]

Variant: +2 obstacles [51]

Snakebird Level 18

Solution [36]

Variant: +2 obstacles [89]

Snakebird Level 24

Solution [27]

Variant: +1 obstacles [58]

Snakebird Level 32

Solution [22]

Variant: +1 obstacles [38]

Snakebird Level 44

Solution [37]

Variant: +1 obstacles [65]

© Nathan Sturtevant, All rights reserved.