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)
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.
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 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.
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?
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.