Pathfinder

Team: Opportunity

This project is the winner of Best AI and ML Project of Codeavour 2020 AI

Project Details

Team Details

  • Member 1: Gaurav Shukla
  • Age Group: group_3_(14_years_-_17_years_):_participants_falling_in_this_group_must_have_been_born_between_2_october_2003_and_1_october_2007.
  • Country: India
  • School Name: kendriya_vidyalaya_raebareli
  • Partner: not_applicable

Project Explaination

So, first I created the background which is like a grid.

Then after that the user needs to create the walls and put starting and ending points in the grid like in the image below.

Ghgh

Then it finds the path automatically for you.

Hdvy

How my Pathfinder works-

 

Let’s say we have the following maze with the starting position “S” and ending position “E”.

The black colored blocks act as walls and rest the rest of the place is where you can move.

The first thing you need to do is create a list to hold numbers for all of the blocks in your map. Mark or leave the movable blocks with anything like -1 or N etc except a positive (+) number and mark the black blocks with a really high number i used 9999. 

On the end position, mark that square as 1 or 0. In my case i marked it as 1.

Starting on the lowest numbered block on the board, 1, go North one block and if it is not filled in, mark it with the next higher number, 2. From 1, go West one block and if it is not filled in, mark it with the next available number, 3. Repeat for South and East.

Now that you’re done with block 1, go to block 2 and repeat the above given process and after that move to block 3 and repeat and so on until the entire board is numbered.

Eg

Note: Take this image as example. In this image the end is marked as 0.

Now, we have calculated a complete map of the board.

If you’ll notice the block marked “S” has a value of 25. We start with that value when determining which direction to go.

All you have to do is look North, South, East, and West from that point and look for the lowest number. In this case it is to the East and the value is 22.

Your sprite should then move to the block labeled “22” and repeat this process.
From block 22, looking North, South, East, and West, the lowest number is 20 to the East.

Your sprite simply needs to repeat this process until it is at the block marked 0 which is the end and there you go it’s your path.