I have created a map with SDL2 pixel drawing on screen. The map looks like in the picture below:
Red, green and blue blocks are buildings. The black block is where the taxis are going to be parked. The white space are streets. Most buildings have 4 sides. I really do not understand how I can implement A* path finding algorithm here. Lets say the first blue building you see has an address of (0,0) and when you ask the taxi to find path the input should look something like (0,0, S) where 0,0 is the address and S stands for the south side of the building.
The white spaces that are road should be divided in 2 to have 2 sides on the road. And the taxi should follow the right side of the road to reach there.
I have seen people are putting the street in a graph and then using the A* algorithm. But I am having a hard time understanding how I can put this pixel drawn map in a graph. and then find the path where 2 way street will be implemented.
Any help in making me understand how I can fit this map in a graph to implement A*?
#include <stdbool.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <assert.h>
#include <ctype.h>
/* Include external library package */
#include <SDL.h>
#include <SDL_image.h>
#ifndef __STRING
#define __STRING(x) #x
#endif
#define rt_assert(expr, str, ...) \
((void) sizeof ((expr) ? 1 : 0), __extension__ ({ \
if (!(expr)) { \
printf("At function %s in file %s:%d, assert failed: (%s). ", __func__, __FILE__, __LINE__, (#expr)); \
printf("Error: %s.\n",(str)); \
__VA_ARGS__; \
getchar(); \
exit(EXIT_FAILURE); \
} \
}))
#define SEED 10
#define BLOCK_WIDTH 64
#define BLOCK_HEIGHT 64
static const int WINDOW_HEIGHT = 1080;
static const int WINDOW_WIDTH = 1920;
SDL_Window *window;
SDL_Renderer *renderer;
SDL_Surface *window_surface;
enum building{
building_width = BLOCK_WIDTH,
building_height = BLOCK_HEIGHT,
};
enum street {
street_width = BLOCK_WIDTH,
street_height = BLOCK_HEIGHT,
};
enum eight_bit_rgb_color {
red,
green,
blue,
alpha
};
enum taxi_park {
taxi_park_width=4*BLOCK_WIDTH,
taxi_park_height=3*BLOCK_HEIGHT,
taxi_park_pos_x=1664,
taxi_park_pos_y=896,
taxi_park_red=0,
taxi_park_green = 0,
taxi_park_blue = 0,
taxi_park_alpha = 255,
taxi_park_entrance_pos_x = 1664,
taxi_park_entrance_pos_y = 960,
taxi_park_entrance_width = BLOCK_WIDTH,
taxi_park_entrance_height = BLOCK_HEIGHT,
taxi_park_entrance_red=255,
taxi_park_entrance_green = 255,
taxi_park_entrance_blue = 255,
taxi_park_entrance_alpha = 255,
};
int find_top(int *arr, int rand_num, int low, int high) {
int mid;
while(low < high) {
mid = low + ((high - low) >> 1); /* (low+high)/2 */
(rand_num > arr[mid]) ? (low = mid + 1) : (high = mid);
}
return (arr[low] >= rand_num) ? low : -1;
}
int weighted_rand(int *arr, int *freq, int arr_size) {
int prefix[arr_size];
prefix[0] = freq[0];
for (int i = 1; i < arr_size; ++i)
prefix[i] = prefix[i-1] + freq[i];
int rand_num = rand() % prefix[arr_size-1] + 1;
int top_index = find_top(prefix, rand_num, 0, arr_size-1);
return arr[top_index];
}
void draw_buildings(int seed) {
srand(seed);
for (int x = 0; x < WINDOW_WIDTH; x += street_width+building_width) {
int color[] = {0,0,0,255};
int arr[] = {red,green,blue};
int freq[] = {60,30,10};
for (int y = 0; y < WINDOW_HEIGHT; y += street_height+building_height) {
SDL_Rect building = {.x = x, .y = y, .w = building_width, .h = building_height};
int rand_result = weighted_rand(arr,freq,3);
color[rand_result] = 255;
SDL_SetRenderDrawColor(renderer, color[red], color[green], color[blue], color[alpha]);
SDL_RenderFillRect(renderer, &building);
color[rand_result] = 0;
}
}
}
void draw_taxi_park(void) {
SDL_Rect taxi_park = {.x = taxi_park_pos_x, .y = taxi_park_pos_y, .w = taxi_park_width, .h = taxi_park_height};
SDL_SetRenderDrawColor(renderer, taxi_park_red, taxi_park_green, taxi_park_blue, taxi_park_alpha);
SDL_RenderFillRect(renderer, &taxi_park);
SDL_Rect taxi_park_entrance = {.x = taxi_park_entrance_pos_x, .y = taxi_park_entrance_pos_y, .w = taxi_park_entrance_width, .h = taxi_park_entrance_height};
SDL_SetRenderDrawColor(renderer, taxi_park_entrance_red, taxi_park_entrance_green, taxi_park_entrance_blue, taxi_park_entrance_alpha);
SDL_RenderFillRect(renderer, &taxi_park_entrance);
}
int main(void) {
rt_assert( (SDL_Init(SDL_INIT_VIDEO) >= 0), SDL_GetError(), );
window = SDL_CreateWindow( "Taxi Emulator", \
SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED,
WINDOW_WIDTH, WINDOW_HEIGHT, SDL_WINDOW_SHOWN
);
rt_assert(window, SDL_GetError(), SDL_Quit());
rt_assert(SDL_SetHint(SDL_HINT_RENDER_SCALE_QUALITY, "linear"), "Failed to set linear texture filtering",);
renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_ACCELERATED);
rt_assert(renderer, SDL_GetError(),
SDL_DestroyWindow(window),
SDL_Quit()
);
window_surface = SDL_GetWindowSurface(window);
SDL_Event e;
bool quit = false;
while (!quit) {
while (SDL_PollEvent(&e)) {
if( e.type == SDL_QUIT ) quit = true;
}
SDL_SetRenderDrawColor(renderer, 0xFF, 0xFF, 0xFF, 0xFF);
SDL_RenderClear(renderer);
draw_buildings(SEED);
draw_taxi_park();
SDL_RenderPresent(renderer);
}
SDL_DestroyRenderer(renderer);
SDL_DestroyWindow(window);
SDL_Quit();
return EXIT_SUCCESS;
}
I would say each white pixel is a node and each side of a colored pixel is a node.
| | | | |
--O-----O-----O-----O-----O--
| | | | |
| O | O |
| ##### | ##### |
--O--O#####O--O--O#####O--O--
| ##### | ##### |
| O | O |
| | | | |
--O-----O-----O-----O-----O--
| | | | |
| O | O |
| ##### | ##### |
--O--O#####O--O--O#####O--O--
| ##### | ##### |
| O | O |
| | | | |
--O-----O-----O-----O-----O--
| | | | |
Here, the ###
block represents a colored pixel from your image, O
represents a node in the graph and --
or |
are the edges of the graph.
Each side of a building is reachable from the road next to it, and each road pixel is reachable by its neighboring road pixels.