Smoothing Pathfinding on Tile-Based Terrain but Free-Roaming Player

Question

I'm sorry if this is a long post, but I feel as though the details should help clarify gray areas. I'll try and provide a detailed layout of what I'm trying to achieve, what I have so far, and where my questions stand/I'm stuck at.

(Will likely touch up how this post looks when seeing it live properly)

Game Overview:
I'm designing a top-down, single-layer, obstacle-based game that will consist of tile-based terrain (only squares). Players, enemies, and objects, however, will be capable of free-roaming and do not snap to any grid. Players, in particular, will vary in sizes and models, so as a generalization they could be circles, triangle, squares, X's, etc.

Since pathfinding is going to rely on solidity, this is the layout I am aiming for:

• Tiles will always be solid or not solid.
• Players and enemies will never be solid.
• It would be nice for objects to go either-or, but if not they can be non-solids.

My Progress:
I've got the the grid-based terrain set up in a Tile[][] design. Since there's only 1 tile per (x,y) coordinate, this allows for clean referencing. Tiles, however, could change via triggers very seldom. So a non-solid Grass tile could turn into a solid Stone tile that is impassible.

Player movement via the mouse is in place. Although this will likely get overwritten with the pathfinding, it currently works with moving the player from point A to point B. The player class has its pixel-position, image, scale, and speed. A player will be 1 grid unit in size (currently 40x40px) and scaled from there. So 0.5 scale is always 20x20px.

Minor hit box detection is in place with bounding boxes as a very general design. Later this will likely get changed to a pixel-checking hitbox method.

My questions/concerns:
My main question for reference is which pathfinding method(s) can I use to know that my unit that isn't based on a grid can move through my map properly and not have clipping? Keeping in mind again that the player can vary in size and tiles can change solidity.

I've spent the past few days looking into pathfinding methods. I've looked into A*, HAA*, HPA*, NavMeshes, and lightly into things like D* and Dijkstra's algorithm. However, pathfinding in general is brand new to me when it comes to something that doesn't move directly on a grid.

Reference material:

The 2x2 teal box is the player. The green 2x2 is the goal. The dots are where the player's top left would be if he went on the grid one square at a time. The gold line is what I'd like to path like.

This HPA* method seems like it'd work, but I'm not sure how to get the path smoothing to work. Would I just constantly see if the next point in the list is something I can go directly to without clipping and remove it if I can?

End Comments:
I'm not sure if posting some structural code here would provide any benefit as my issue is with the methodology of how to approach this rather than what I have so far.

I do know there are some topics involving this. I cannot link since I'm limited to two, but I see one here titled 'Tile-wide extent tracing on a grid' that seems to ask a similar thing. The problem with almost all example pictures of pathfinding methods uses a size-less example. (Except this one, but it still clips in one of its turns)

The unit itself will have a turning speed involved, but I don't think that should affect the cornering. For the most part, I don't need smooth, car-like, turning if it's more work.

Please let me know if there's anything I missed, I should clear up, or if I've overlooked a topic that went deep into exactly what I'm asking. It's late and I wanted to get something up on here while I continue my search. I just feel lost in this implementation.

Answer 1

Size and fit can be taken care of the heuristic that declares whether a move is valid during the path finding. Once the path itself is generated it's then up to a localized movement function to handle not bumping into things on the way, called path smoothing. Maybe paths with smoothing will help generate some ideas that work for you.

The last time I did this I used the path as a kindly suggestion and did local look-ahead to straighten out the zig-zags and then some hacking to always go wide around corners and allow colliding and sliding against the outside in favor of hooking up against the inside of the corner.

If at any point after a particular path has been generated the grid changes you must regenerate the path.

Answer 2

I got good results by using A* then from the last node i was casting rays back to each node in the path, checking height of terrain on each ray to determine if it was still ok to walk there (you can add your own logic here, water, enemies, buildings ... etc ... mine was if height difference was less than 1 unit per 1 unit distance, then you can't walk), once i hit a node that fails the ray test, i used last node that passed the ray test, and cast rays from it to the remaining nodes, iterate till reaching the start point, and got nice paths, on open maps you will get a straight line between N-start and N-end

A* = N(start), N1, N2, N3 N4 N5 ... N(end)

for i = end ; i >= start ; i--
    ray-test = true 
    ii = i // ray must pass by default between 2 adjacent nodes

    while ray-test == true && ii != start
        ii--
        from N(i) cast ray to N(ii)
        ray-test = check path along the ray N(i) --> N(ii)

    //here N(ii) failed the ray-test, 
    //thats how we got outside the loop
    //ignore all nodes between the end/destination
    //node than the last node that fulfills the ray test

    N(i).parent = N(ii+1)