Designing a versatile pathfinding system for a 2D game with complex movement

[small nimbus]

I'm working on something inspired by the N games (N, Nv2, N+, N++), which are platforming games where you can walljump, slide, etc. I'm trying to add my own ideas to this concept and one of the things I'm trying to get working is an enemy that can chase the player.

Due to the complex nature of the movement (see attached gif), it has been very difficult trying to come up with a pathfinding solution that can support wall jumping and such. I want a solution that's completely dynamic and works on any map without any need of manual input (ie placing nodes on walls or whatever).

One solution I tried was to have a linked list of nodes in the tilemap data structure that were created as the player moved through the map. The nodes contained data of the player's input at that time. This allowed the AI to essentially retrace the player's movement perfectly but it was too obvious that the AI was just copying the player's movement and not actually following a calculated path.

Has anyone had to design something similar to this? How did you solve it? Or does anyone know of a game (preferably open source) that solves a similar issue?

There's not much I can really share in the form of code that would be useful. This is what my Tilemap data structure looks like:

typedef struct Tilemap {
    int *tiles;             // 2D array of tile indices (flattened to 1D)
    int **tileEdges;        //Edge/corner info for broadphase collision detection
    //Format is:
    /* 
        tileEdges={
            {top, right, bottom, left, topright, topleft, bottomright, bottomleft} // For tile 0
            {top, right, bottom, left, topright, topleft, bottomright, bottomleft}  // For tile 1
            ...
        }
    */
   //Where edge values are 0 for no edge, 1 for solid edge, and 2 for interesting edge (like a half tile) that requires special collision handling

    //Doubly linked list of nodes for pathfinding
    Node* pathfindingNodes;

    int width;              // Width of the tilemap in tiles
    int height;             // Height of the tilemap in tiles
    int tileSize;           // Size of each tile in pixels
} Tilemap;

[final sandal]

why not place bounding boxes wherever the rectangles are?

then the enemy can pathfind to u using the bounding boxes

[small nimbus]

I don't think you understand the problem I'm facing.

[final sandal]

i've never worked with pathfinding ever, i js shared my opinion 😅

[hoary bough]

This is an interesting problem. all the Player-like NPCs in platformers I can think of are clearly player recordings, (Badeline from Celeste is the one concrete example I can remember but I know I've seen it more than that) or follow very simple routes with scripted actions (Ink mario from Sunshine was this, I think? Just follow a set path and jump when prompted by a trigger placed before each ledge on his route?)

introducing a chaser to your platformer is a proven Great Idea™, I think my favorite example is Simpleflips's green demon challenge, but of course that's a flying enemy, not a fully player-like NPC.

Although, the consequences to the player aren't too much different if the chaser is like them or not, so maybe you should add an enemy that flies and uses normal A* pathfinding through the level just to test the concept. If that needs extra work / level design considerations to be fun, the full plan will too.

anyway, my thought for pathfinding would be to first detect patches of the level that are easy to traverse, flat platforms and ramps and such, and treat each one as a "node" and highlight them in the map editor, then have the map maker record gameplay of each way to get from each node to each adjacent node. The NPC can use a simple "hold right" type AI to get to the 'exit point' of it's current zone, then repeat the recorded inputs to perform the zone crossing.