so_long 과제에서, 플레이어 위치부터 출구 까지 도달 가능한지 경로 유효성을 판단해야 한다.

11111
100E1
10001
10001
1P001
11111

DFS or BFS?

bfs를 선택 할 이유가 없음. 재귀를 쓸 필요도 없고, stack을 써서 dfs를 돌리면 된다. 지역변수로 stack 배열 메모리를 잡고 싶으나, 맵 최대사이즈가 명시된 것이 없으므로 성능을 포기하고 malloc하여 메모리 잡기. (사실 인라인 어셈으로 push/pop 써서 구현해도 된다. 빠르고 가변적이다)

t_xy *const	stack = malloc(game->map_col * game->map_row * sizeof(t_xy));
int			    top;

if (get_obj(game, now.row + 1, now.col) == '0') // up
			push(stack, &top, now.row + 1, now.col);
if (get_obj(game, now.row - 1, now.col) == '0') // down
			push(stack, &top, now.row - 1, now.col);
if (get_obj(game, now.row, now.col + 1) == '0') // left
			push(stack, &top, now.row, now.col + 1);
if (get_obj(game, now.row, now.col - 1) == '0') // right
			push(stack, &top, now.row, now.col - 1);

“한 칸은 여러 번 stack에 들어갈 수 없다.” 라고 정하고 구현하면 stack 크기는 맵 최대 크기를 넘을 수 없다.

IS_VISITED

이제 필요한 것은 “여기 방문한 적이 있던가” 를 저장해야 하는데, malloc 한 번 더 하기가 싫다…

자. map은 char로 이루어져 있다. extended ascii가 아니라면 제일 왼쪽 sign 비트를 사용하지 않는다.

제일 왼쪽 비트를 is_visited 플래그로 쓰면 된다.

이러면 추가 할당은 필요하지 않는다.

#define MSB (0x80) // (1 << (CHAR_BIT - 1))

// 방문
map[i][j] |= MSB;

// 방문 판단
if ((map[i][j] & MSB) != 0)
{
		// 기존 글자
		return map[i][j] & ~MSB;
}

so_long 과제 여담

frame을 0부터 59까지 반복하도록 짜야했는데,

// 1
frame = frame % 60;

// 2
++frame;
if (frame >= 60)
		frame = 0;

위와 같이 두 방식이 있는데, 아래가 더 빠르다.

%는 대충 26클럭 정도 걸리는데, if도 분기문이라 만만치않게 느리지만 60이 될 때만 분기하기 때문에 분기예측률이 높아서 아래가 더 낫다.