CodeKnight & Chainik
Chainik
Hey CodeKnight, I've been messing around with building a tiny maze‑solver robot using a microcontroller, and I think we could make it super fast with some clever code—what do you think about tackling a path‑finding puzzle together?
CodeKnight
Sounds good, let’s get the algorithm tight. A* or Dijkstra on a grid, then we can micro‑optimize the loop. Just give me the maze size and any constraints, and I’ll write the core logic.
Chainik
Alright, let’s do a 10 by 10 grid, no diagonal moves, just straight up, down, left, right. All cells are open except a few random walls, say 20% blocked. That should give us a decent challenge to squeeze the A* loop in micro‑seconds. Ready to see the code?
CodeKnight
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#define W 10
#define H 10
#define MAX 256
typedef struct {int x,y;int f,g,h;} Node;
int grid[H][W];
int closed[H][W];
Node open[MAX];
int openCount=0;
int heuristic(int x,int y){return abs(x-(W-1))+abs(y-(H-1));}
bool inBounds(int x,int y){return x>=0&&x<W&&y>=0&&y<H;}
bool walkable(int x,int y){return inBounds(x,y)&&grid[y][x]==0;}
int openMin(){int best=INT_MAX,i=-1;for(int j=0;j<openCount;j++)if(open[j].f<best){best=open[j].f;i=j;}}return i;}
void addOpen(int x,int y,int g){Node n={x,y,g,heuristic(x,y),g+heuristic(x,y)};open[openCount++]=n;}
void aStar(){
openCount=0;for(int y=0;y<H;y++)for(int x=0;x<W;x++)closed[y][x]=0;
addOpen(0,0,0);
while(openCount){
int idx=openMin();if(idx==-1)break;Node n=open[idx];
if(n.x==W-1&&n.y==H-1){printf("path found cost %d\n",n.g);return;}
open[idx]=open[--openCount];
closed[n.y][n.x]=1;
int dirs[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
for(int d=0;d<4;d++){int nx=n.x+dirs[d][0],ny=n.y+dirs[d][1];
if(!walkable(nx,ny)||closed[ny][nx])continue;
int ng=n.g+1;
addOpen(nx,ny,ng);
}
}
printf("no path\n");
}
int main(){
srand(1);
for(int y=0;y<H;y++)for(int x=0;x<W;x++)grid[y][x]= (rand()%100<20)?1:0;
grid[0][0]=grid[H-1][W-1]=0;
aStar();
return 0;
}
Chainik
Looks solid! Just a few quirks: your `openMin()` function’s curly braces are a bit off—make sure the return is inside the loop block, otherwise it returns `-1` every time. Also, the `addOpen` logic could duplicate nodes; you might want to check if a node is already in the open list before pushing it. And hey, using a plain array for the open set is fine for 10x10, but for bigger grids you could swap in a binary heap to cut that linear search down. Good luck, and keep that tinkering spirit going!
CodeKnight
Thanks for the catch on openMin, that typo will screw up the whole loop. I’ll add a check to avoid duplicates in the open list, and for bigger maps I’ll switch to a binary heap right away. Got the 10x10 patch ready now, let’s push it to the board. Happy hacking!