A* custom heuristic function about libtcod HOT 8 OPEN

from libtcod.

Thanks for sharing your own examples.

A malloc on each queue push isn't good for performance. It harms threading and memory locality.

It's tricky to figure out what I'd even want to do. I really want something that's flexible.

Maybe if I redid the C pathfinder I could make one that takes a C callback to define the graph. I don't think I'll do this until I've implemented something similar in C++, or maybe I can try to backport the complicated Python-tcod pathfinder.

from libtcod.

I've been in the middle of a rewrite of the pathfinder for a long time now. I haven't been happy with what I've done so far, and my plans have been ambitious.

I want to remove the 2D limit, allow a custom heuristic function, and a custom graph function.

The C++ templates in the src/libtcod/pathfinding directory do what I want, but I need to somehow port these to C99.

from libtcod.

Thinking back on this I should have just made the C++ templates more accessible and not worried about what was available in C.

It was really easy to set up a new pathfinder in C++. The hard part was that I need to figure out how to handle the inputs and outputs of the pathfinding computation data, since there's no standard multi dimensional array type in C++.

from libtcod.

from libtcod.

from libtcod.

The main dependency I used was a priority queue I believe.

This is the main part. It's trivial to implement a pathfinder after you have access to a good priority queue. I have one in libtcod but the interface is too weird and I don't want to lock it in by making it public.

I know in my haskell roguelike I pass in a function to the A* algorithm which returns all neighboring points for a given point.

I'll need to do this for C sometime. I've previously done it with C++ templates but it might be easy enough to make a simple C callback work in a similar way. I'm still missing a good C container for the array of distances/path-costs.

from libtcod.

Simple things like "what is the size of an index" are not so easy to resolve in C. This is one of the things which made the internal heap queue turn out weird.

from libtcod.