BFS and Voronoi diagrams using bit-shift operations

wlesavo
669 views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

Introduction

Looking for ways to speed up some parts of the search within a game states one would often hear about a mystical "bitshifts" and "bitboards". I found myself in this position and fragmentary knowledge i was able to find in internet did not help much. Maybe there are these types of articles but i just couldn't find one to help me solve even a quite simple tasks. Although we do have some excelent playgrounds from MSmits and emh which were a starting point for me, but for the rest for many things I would have to come to mind by myself. I highly recommend checking these playgrounds prior to this article, since we will not go into much details about the common BFS itself.

Wrapping up, in this playground I will try to demonstrate a simple way to think about BFS using bitboards on example of three different CG games: Great Escape, Amazonial and Line Racing going for somewhat diverse goals but showcasing the same idea. In Great Escape we will find the length of a shortest path, which is a main heuristic in evauation function for this game. In Amazonial and Line Racing we will calculate the Voronoi diagramms (number of cells one player can reach faster than another and vise versa), which are also the main heuristics for those games while being the most time consuming operations in simulation. The difference for a Line Racing is having up to 4 players and the fact that the board can't be reasonably stored in a single integer value since it has 600 cells.

I would also encourage more experienced users to point out to any mistakes I made or a bad practicies I had accidentally used.

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content