Skip to main content

Indie game storeFree gamesFun gamesHorror games
Game developmentAssetsComics
SalesBundles
Jobs
TagsGame Engines

AI and A*pathfinding

A topic by Joobleboo created May 29, 2023 Views: 478 Replies: 11
Viewing posts 1 to 10

I am starting a school project and need to make use of the A* pathfinding alg in unity. I have to code it manually and do not know where to start, does anyone have any help or advice??

The A* pathfinding algorithm is among the most documented algorithms out there. What exactly are you having trouble with?

Moderator moved this topic to General Development
Moderator(+3)

Also, since this is for school, maybe ask your teacher?

My teacher isnt allowed to help, Im having trouble with where to start with the algorithm, with regards to connecting nodes and how to identify each node and their cost.

(1 edit)

A*‘s job isn’t to connect the nodes; it’s already given a connected, weighted graph.

Again: A* is extremely documented. Wikipedia even has pseudocode. Have you looked it up and gotten stuck? If so, where?

I understand the algorithm and the theory but it is the use of a tielmap that gets me, I'm not sure how I'd apply a cost to each tile and how to access the tiles in a script 

(2 edits)

The way I handled this was to only create nodes as the algorithm went. The tilemap was your usual multi-dimensional array (as I assume yours is), and only when added to the open set was a tile turned into a graph vertex. This way, the graph is always as small as it needs to be for the algorithm to work.

With a tilemap you have no need to store an entire graph data structure, because the tilemap has a clear pattern. For instance, the for each neighbor of current part of Wikipedia’s pseudocode is as simple as indexing to the neighboring tiles of the tilemap ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1), etc.)

The heuristic function can just be the straight-line distance to the target tile.

I have example code, but it is in C, is 3D, and it’s my C code, which makes it naturally a mess. Not sure if you’d like to see it.

I think it'd help seeing your code if you wouldn't mind. I think the bulk of my problem comes from working with the unity tilemap, how do I access neighbouring nodes from a script?

(3 edits)

A star in a tile map? That's unusual... Is it a square tile? Hexa-tile?

If the tile map is empty then the optimal path is always a straight line, if not then you should build your graph out of the walkable tiles.

So, accessing the neighbors works by converting or at least treating the tiles like nodes. For instance, if we're talking square tiles, and your tile in question has a "wall" just below it, then this tile has a list of 3 neighbors, one on each side and one right above it. You will have to do that iteratively, generating a list  of neighbors for each tile/node (it may be inefficient but good enough for a school work), for all your tiles in the map before you run the A star, got it?

(2 edits)
struct PathPoint {
	// Node position
	int16_t x, z, y;
	// Parent node position
	int16_t pX, pZ, pY;
}

static int cmpeq(struct PathPoint a, struct PathPoint b) {
	return a.x == b.x && a.z == b.z && a.y == b.y;
}

// This function checks if the node is free (1 = free)
static int walk(struct PathPoint p, int dx, int dy, struct PathPoint *ret) {
	p.pX = p.x, p.pZ = p.z, p.pY = p.y;
	p.x += dx, p.y += dy;
	p.cost++;
	*ret = p;
	
	// Clearly it must be in-bounds
	if(p.x >= 0 && p.x < game_W && p.y >= 0 && p.y < game_H) {
		// Game-specific logic here to determine which tiles can be walked on
		return 1;
	} else return 0;
	
	// My game was 3D so this made entities fall downwards
	size_t ind = GAME_POINTTOINDEX(p.x, p.z, p.y);
	while(!game_Map[ind] && ret->z > 0) {
		ind -= game_H;
		ret->z--;
	}
	if(game_Map[ind]) ret->z++;
	
	return 1;
}

// Returns index if exists, else -1
static int in_list(struct PathPoint p, struct PathPoint *list, size_t listLength) {
	for(size_t i = 0; i < listLength; i++) {
		if(cmpeq(list[i], p)) return i;
	}
	return -1;
}

// My heuristic function (chess distance)
static uint32_t chessdist(struct PathPoint a, struct PathPoint b) {
	return max32(max32(abs32(a.x - b.x), abs32(a.y - b.y)), abs32(a.z - b.z));
}

size_t pathfind(struct PathPoint start, struct PathPoint end, struct PathPoint **result) {
	// List of open nodes, in order from least to most costly
	size_t openCount = 1;
	struct PathPoint *open = malloc(sizeof(*open));
	*open = start;
	
	size_t closedCount = 0;
	struct PathPoint *closed = NULL;
	
	while(openCount) {
		// Get first (least costly) node from open set
		struct PathPoint p = open[0];
		memmove(open, open + 1, sizeof(*open) * --openCount);
		
		closed = realloc(closed, sizeof(*closed) * ++closedCount);
		closed[closedCount - 1] = p;
		
		if(cmpeq(p, end)) { // If p == end (we've found a path, now return it)
			size_t padhCount = 1;
			struct PathPoint *padh = malloc(sizeof(*padh) * padhCount);
			padh[0] = p; // Starting with p (not end cause p has proper parent information)
			
			// Go back through all the parent information to reconstruct the path
			do {
				int idx = in_list((struct PathPoint) {.x = padh->pX, .y = padh->pY, .z = padh->pZ}, closed, closedCount);
				padh = realloc(padh, sizeof(*padh) * (padhCount + 1));
				memmove(padh + 1, padh, sizeof(*padh) * padhCount++);
				*padh = closed[idx];
			} while(!cmpeq(*padh, start));
			
			free(open);
			free(closed);
			
			*result = padh;
			return padhCount;
		}
		
		// Try all eight neighbours
		struct PathPoint candidate;
		for(int dx = -1; dx <= 1; dx++) {
			for(int dy = -1; dy <= 1; dy++) {
				if(walk(p, dx, dy, &candidate) && in_list(candidate, closed, closedCount) == -1) {
					// We can walk here!
					
					candidate.cost += chessdist(candidate, end); // Apply heuristic
					
					// No point in adding to the open list if it is already there
					int openListID = in_list(candidate, open, openCount);
					if(openListID == -1) {
						// Add to the open list
						// Find the correct index to keep it sorted
						int i;
						for(i = 0; i < openCount; i++) {
							if(open[i].cost > candidate.cost) {
								break;
							}
						}
						open = realloc(open, sizeof(*open) * ++openCount);
						memmove(&open[i + 1], &open[i], sizeof(*open) * (openCount - i - 1));
						open[i] = candidate;
					} else {
						// Update parent information if we've found a shorter path to this node
						if(candidate.cost < open[openListID].cost) {
							open[openListID].cost = candidate.cost;
							open[openListID].pX = p.x;
							open[openListID].pZ = p.z;
							open[openListID].pY = p.y;
						}
					}
				}
			}
		}
	}
	
failed:
	free(open);
	free(closed);
	*result = NULL;
	return 1;
}

I’ve added comments, but if I’m honest this isn’t much different to the pseudocode in Wikipedia.

From a C perspective there’s plenty of room for optimization, but it works. In C# there’s almost certainly an automatic sorted list/set or priority queue class in the standard library.

I thought I'd manage to make sense of the code🤣I can't because I've never seen a single line of C before😬from looking into it, I don't know what the nodes would be for my algorithm? Would I use a tilemap or would soemthing else be better to use? 

(2 edits)

Forget the abstract concept of “nodes”. You’re using tiles, so just think of them like that.

You need a set of “open tiles” and “closed tiles”, and both kinds hold the position of said tile, the position of its parent tile, and the cost of getting to that tile.

When the algorithm starts, your open tile set contains the starting point. After that the algorithm will naturally expand outwards by querying neighboring tiles, which are very easy to find on a tilemap.