C 팁에서 A * 및 ALT 경로 찾기
작업중인 게임에 길 찾기를 추가합니다. 그것은 주로 reb blob games 의 길 찾기 기사에서 제안한대로 A *를 사용 했습니다 .
작동하지만 그렇게 빠르지는 않습니다.
(현재) 균일 한 이동 비용을 갖는 정사각형 그리드 맵이지만 앞으로 경로가 적 유닛 등을 피할 수 있도록 가중치를 추가 할 것입니다.
다음은 몇 가지 코드입니다.
다음은 stb stretchy_buffer.h의 영향을 많이받는 FIFO-queue 헤더입니다 .
#ifndef QUEUE_H
#define QUEUE_H
#include <stdlib.h>
#include <string.h>
#include <assert.h>
// Entire data block
#define queue_raw(a) ((int*) (a)-3)
// Number of elements queue can hold
#define queue__s(a) (queue_raw(a)[0])
// Index of the first element
#define queue__f(a) (queue_raw(a)[1])
// Number of queued elements
#define queue__c(a) (queue_raw(a)[2])
#define queue_count(a) ((a) ? queue__c(a) : 0)
#define queue_empty(a) (queue_count(a)==0)
#define queue_push(a,v) (queue__maybegrow(a,1), (a)[queue__norm(a, (queue__f(a)+(queue__c(a)++)))]=v)
#define queue_append(a,n) (queue__maybegrow(a,n), queue__c(a)+=(n), &(a)[queue__c(a)-n])
#define queue_peek(a) ((a) ? (a)[queue__f(a)] : 0)
#define queue_pop(a) (queue_empty(a) ? 0 : (queue__c(a)--, queue__f(a)=queue__norm(a,queue__f(a)+1), ((a)[queue__f(a) ? queue__f(a)-1 : queue__s(a)-1])))
#define queue_last(a) (queue_empty(a) ? 0 : (a)[queue__norm(queue__f(a)+queue__c(a))])
#define queue_poplast(a) (queue_empty(a) ? 0 : (queue__c(a)--, (a)[queue__norm(queue__f(a)+queue__c(a))]))
#define queue_free(a) ((a) ? free(queue_raw(a)),0 : 0)
#define queue__norm(a,i) (((i)%queue__s(a)+queue__s(a))%queue__s(a))
#define queue__grow(a,n) queue__growf((void*) &(a), (n), sizeof(*(a)))
#define queue__needgrow(a,n) ((a)==0 || queue_count(a)+n > queue__s(a))
#define queue_resize(a,n) (queue__maybegrow((a),(n)))
#define queue__maybegrow(a,n) (queue__needgrow((a),(n)) ? queue__grow((a),(n)) : (void)0)
static void queue__growf(void** arr, int increment, size_t itemsize) {
// Grow the size of *arr by increments*itemsize bytes.
// Does not change queue__c(*arr)
int c = queue_count(*arr);
if (*arr && !c) queue__f(*arr) = 0;
int s = *arr ? queue__s(*arr) : 0;
int f = *arr ? queue__f(*arr) : 0;
int m = c + increment;
assert(m > s);
if (f) {
// Reallocate the queue with the first element at index 0
void* buf = malloc(itemsize*m + sizeof(int)*3);
assert(buf);
if (buf) {
void* arr_buf = (void*) ((int*) buf + 3);
if (f + c <= s) {
memcpy(arr_buf, (unsigned char*)(*arr) + f*itemsize, itemsize * c);
} else {
memcpy(arr_buf, (unsigned char*)(*arr) + f*itemsize, itemsize * (s-f));
memcpy((unsigned char*) arr_buf + itemsize*(s-f), *arr, itemsize * (f+c-s));
}
queue__s(arr_buf) = m;
queue__f(arr_buf) = 0;
queue__c(arr_buf) = c;
queue_free(*arr);
*arr = arr_buf;
}
} else {
void* buf = realloc(*arr ? queue_raw(*arr) : 0, itemsize*m + sizeof(int)*3);
assert(buf);
if (buf) {
*arr = (void*) ((int*) buf + 3);
queue__s(*arr) = m;
queue__f(*arr) = 0;
queue__c(*arr) = c;
}
}
}
#endif
그리고 내 우선 대기열 :
#ifndef PRIORITY_QUEUE_H
#define PRIORITY_QUEUE_H
typedef struct {
int v;
int p;
} pqueue_pair;
struct pqueue {
int size;
int count;
pqueue_pair* data;
};
void pqueue_push(struct pqueue* h, int v, int p);
int pqueue_pop(struct pqueue* h);
#endif
#ifdef PRIORITY_QUEUE_IMPLEMENTATION
static inline void swap(pqueue_pair* a, pqueue_pair* b) {
pqueue_pair tmp;
memcpy(&tmp, a, sizeof(pqueue_pair));
memcpy(a, b, sizeof(pqueue_pair));
memcpy(b, &tmp, sizeof(pqueue_pair));
}
static void heapify(struct pqueue* h, int i) {
int largest = i;
while (true) {
int l = 2*i + 1;
int r = l + 1;
if (l < h->count && h->data[l].p < h->data[largest].p) largest = l;
if (r < h->count && h->data[r].p < h->data[largest].p) largest = r;
if (largest != i) {
swap(h->data+largest, h->data+i);
i = largest;
} else {
break;
}
}
}
void pqueue_push(struct pqueue* h, int v, int p) {
if (h->count >= h->size) {
h->count --;
printf("Overflowing pqueue of with %d elements! Last element as priority of %d\n", h->size, h->data[h->count].p);
}
h->data[h->count].v = v;
h->data[h->count].p = p;
h->count ++;
if (h->count > 1) {
for (int i=h->count/2-1; i>=0; i--) {
heapify(h, i);
}
}
}
int pqueue_pop(struct pqueue* h) {
assert(h->count);
int v = h->data[0].v;
h->count --;
memcpy(h->data, h->data+h->count, sizeof(pqueue_pair));
if (h->count > 1) {
heapify(h, 0);
}
return v;
}
#endif
#endif
마지막으로 코드 자체 (적어도 대부분, 게임 관련 내용은 잘라 냄) :
uint8_t* obstacles = 0;
unsigned int obstacles_size = 0;
#define MAX_LANDMARK_DISTANCE 0xff
uint8_t* landmarks = 0;
int* landmark_positions = 0;
int num_landmarks = 0;
int landmark_size = 0;
// Functions for but shifting into an array of single-bit bools.
// I don't know if the speed difference compared to normal
// indexing, but I assume the size difference is worth it?
static inline uint8_t get_obstacle(int i) {
assert(i/8 < obstacles_size);
return obstacles[i/8] & (1 << i%8);
}
static inline void set_obstacle(int i) {
assert(i/8 < obstacles_size);
obstacles[i/8] |= 1 << i % 8;
}
static inline void unset_obstacle(int i) {
assert(i/8 < obstacles_size);
obstacles[i/8] = ~((~obstacles[i/8]) | 1 << i%8);
}
static int get_neighbors(int* neighbors, int i, int s) {
// Fill neighbors with flattened coords of tiles adjacent to i and return the count
assert(i >= 0 && i < s*s && s >= 0);
int x = i % s;
int y = i / s;
int count = 0;
if (x > 0) neighbors[count++] = i-1; // East
if (x < s-1) neighbors[count++] = i+1; // West
if (y > 0) neighbors[count++] = i-s; // North
if (y < s-1) neighbors[count++] = i+s; // South
return count;
}
void update_map(/* Game-specific arguments */) {
// This function is called every time the map
// changes, (i.e., wall is remove, building added/destroyed)
// It happens fairly often.
// Update obstacles here, and allocates them if need be
// Update the landmarks
#define L(i) (landmarks + (i)*landmark_size)
// This part here is rather slow
memset(landmarks, 0xff, num_landmarks*landmark_size*sizeof(*landmarks));
for (int l=0; l<num_landmarks; l++) {
assert(landmark_positions[l] >= 0 && landmark_positions[l] < size);
L(l)[landmark_positions[l]] = 0;
int* queue = 0;
queue_resize(queue, map->size * 3);
queue_push(queue, landmark_positions[l]);
while (queue_count(queue)) {
int current = queue_pop(queue);
assert(L(l)[current] < MAX_LANDMARK_DISTANCE);
int neighbors[4];
int neighbors_count = get_neighbors(neighbors, current, map->size);
for (int n=0; n<neighbors_count; n++) {
int next = neighbors[n];
if (get_obstacle(next)) continue;
int new_cost = L(l)[current] + 1;
if (new_cost < L(l)[next]) {
L(l)[next] = new_cost;
if (new_cost < MAX_LANDMARK_DISTANCE) queue_push(queue, next);
}
}
}
queue_free(queue);
}
#undef L
}
static inline int distance_heuristic(int a, int b, int w) {
return abs(a%w - b%w) + abs(a/w - b/w);
}
static inline int heuristic(int a, int b, int w) {
int d = distance_heuristic(a, b, w);
for (int i=0; i<num_landmarks; i++) {
int da = landmarks[i*landmark_size + a];
int db = landmarks[i*landmark_size + b];
int dd = abs(da - db);
if (dd > d) {
d = dd;
}
}
return d;
}
void nav_path_find(int map_size, int sx, int sy, int gx, int gy, uint16_t* path_out, uint8_t* path_length, uint8_t max_path) {
int start = sy*map->size + sx;
int goal = gy*map->size + gx;
// The maps are always square
int size = map_size * map_size;
const int pq_size = map->size*3;
pqueue_pair pq_data[pq_size];
for (int i=0; i<pq_size; i++) pq_data[i].p = -1;
struct pqueue pq = {.size=pq_size, .count=0, .data=pq_data};
pqueue_push(&pq, start, 1);
// Create the closed list the size of the entire map which stores
// the flattened Cartesian coordinates of the previous tile such that
// y * map_width + x = i
// and
// x == i % map_size && y == (int) i / map_size
int came_from[size];
for (int i=0; i<size; i++) came_from[i] = -1;
came_from[start] = 0;
uint16_t cost[size];
memset(cost, 0xff, sizeof(*cost) * size);
bool found_path = false;
while (pq.count > 0 && !found_path) {
int current = pqueue_pop(&pq);
assert(came_from[current] >= 0);
if (current == goal) {
found_path = true;
}
int neighbors[4];
int neighbors_count = get_neighbors(neighbors, current, map->size);
for (int n=0; n<neighbors_count; n++) {
int next = neighbors[n];
if (get_obstacle(next)) continue;
int new_cost = cost[current] + 1;
if (came_from[next] < 0 || new_cost < cost[next]) {
cost[next] = new_cost;
pqueue_push(&pq, next, new_cost + heuristic(next, goal, map_width));
came_from[next] = current;
}
}
}
// Here we trace the path back and return the first `max_path` steps
}
맵 장애물은 상당히 동적이며 게임 과정에서 변경되므로 맵 편집기에 배치 된 랜드 마크는 유용하지 않거나 전체적으로 잡초로 둘러싸 일 수 있습니다.
랜드 마크를 동적으로 배치하고 일반적으로 내 코드를 더 빠르고 / 더 예쁘게 만드는 제안 / 방법 / 리소스를 주시면 감사하겠습니다.
내가 가진 한 가지 아이디어는 각 타일의 힙 위치에 대한 인덱스를 보유하는 맵 크기의 배열을 갖는 것이므로 다음과 같이 항목의 우선 순위를 변경할 수 있습니다.
int pq_indices[size];
for (int i=0; i<size; i++) pq_indices[i] = -1;
// Then later when looping through neighbors
if (pq_indices[next] != -1) {
// Push it
} else {
pq_data[next].priority = new_priority;
pqueue_update();
}
그리고 나는 그 배열을 추가하여 pqueue
밀거나 터뜨 리거나 힙을 줄 때 어떻게 든 업데이트 될 것입니다.
또한지도가 64x64 타일 (작은지도)에서 512x512 타일 (거대한지도) 사이에있을 수 있다는 점도 주목할 가치가 있습니다.
답변
그래서 제가 생각한 한 가지는 맵 크기가 아닌 휴리스틱을 기준으로 우선 순위 대기열의 크기를 기준으로하는 것입니다.
const int pq_size = heuristic(start, goal, map_size) * 3;
또한 우선 순위 큐가 오버플로되면 새 요소가 더 나은 경우 마지막 요소 만 다시 작성합니다.
if (h->count >= h->size) {
printf("Overflowing pqueue of with %d elements! Last element as priority of %d\n", h->size, h->data[h->count-1].p);
if (h->data[h->count-1] <= p) {
return;
}
h->count --;
}