A* custom heuristic function

[MichaelMackus]

It would be helpful to add a parameter to the pathfinding for a custom heuristic function. I'm not too familiar with the internals of the TCOD pathfinding, but looking into it it looks like you're just using straight euclidian distance for the heuristic. Perhaps adding a function argument could help simplify this, I was thinking something like:

TCOD_path_t TCOD_path_new_using_map(TCOD_map_t map, float diagonalCost, TCOD_path_func_t heuristicFunc)

This could also further simplify things by eliminating the need to maintain a separate set of functions for the Dijkstra algorithm (could just use the NULL case for heuristicFunc here). Just an idea, I've implemented something similar and it seems to work pretty well.

[HexDecimal]

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.

[HexDecimal]

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++.

[MichaelMackus]

I did a pretty basic pathfinder via native C with no issues. It is a bit messy but using pointer functions I can add a custom heuristic with little issues. The main dependency I used was a priority queue I believe.

…

On Mon, Aug 9, 2021 at 10:23 PM Kyle Benesch ***@***.***> wrote: 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++. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#60 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAFT7CTK3WUJGHZ2R4ZD2ZTT4CZWNANCNFSM4MZG4WGQ> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&utm_campaign=notification-email> .

[MichaelMackus]

Ah, I just noticed you're expanding it to 3d. Perhaps thinking of this more functionally would help more - I know in my haskell roguelike I pass in a function to the A* algorithm which returns all neighboring points for a given point. This way I could avoid any more complicated data structures. Might be something to think about. On Wed, Aug 11, 2021 at 8:50 PM Michael Mackus ***@***.***> wrote:

…

I did a pretty basic pathfinder via native C with no issues. It is a bit messy but using pointer functions I can add a custom heuristic with little issues. The main dependency I used was a priority queue I believe. On Mon, Aug 9, 2021 at 10:23 PM Kyle Benesch ***@***.***> wrote: > 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++. > > — > You are receiving this because you authored the thread. > Reply to this email directly, view it on GitHub > <#60 (comment)>, > or unsubscribe > <https://github.com/notifications/unsubscribe-auth/AAFT7CTK3WUJGHZ2R4ZD2ZTT4CZWNANCNFSM4MZG4WGQ> > . > Triage notifications on the go with GitHub Mobile for iOS > <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> > or Android > <https://play.google.com/store/apps/details?id=com.github.android&utm_campaign=notification-email> > . >

[HexDecimal]

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.

[HexDecimal]

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.

[MichaelMackus]

Feel free to take a look at my library if helpful: https://github.com/MichaelMackus/simplerl/blob/master/lib/ (it is all MIT) It is far from complete and I'm sure there might be some bugs, but so far in the example game it seems to work well. It has very little in terms of external dependencies (I actually was going to use libtcod but it turned out too heavy for my use-case) and the queue is extremely simple. I don't really see a need to make the queue very complicated - during prototyping I tried using your queue code but it turned out unnecessarily complex for what I'm doing in the pathfinder. I'm actually in the process of some improvements but hopefully the code makes sense & might give some inspiration at least. It is definitely constrained to 2d and C-only currently, though (I still need to fix embedding in C++).

…

On Wed, Aug 11, 2021 at 9:23 PM Kyle Benesch ***@***.***> wrote: 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. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#60 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAFT7CQ7OTG5H6XGT6FROQLT4NEDXANCNFSM4MZG4WGQ> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&utm_campaign=notification-email> .

[HexDecimal]

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.