I'm trying to program a very basic path finding implementation, but it's hopelessly inefficient, because I have no good way to query a location in the world to see if it's valid to move there. What I do now is, from the starting position, recursively cast a ray in 8 directions to flood fill the screen and for every vector loop over all the collision rectangles that are only present on the screen (so I filtered the entities already to only contain those that are visible) and check if the rectangle contains the vector.
To give an indication of how slow it is, the game loop takes on average 50 000 cycles/frame, and when path finding it takes between 500 000 and 5 000 000 cycles/frame.
This is the most naive way to implement this I'm sure. :P But I'm stuck thinking in a certain way and need a push in another direction. I don't want to use tiles, or at least I don't think so because the entities have no integer coordinates.
Basically I just need to efficiently query a position, I think that's the main problem. However, I couldn't find a source I understand to implement a quadtree and how to reduce rectangles into a polygon mesh.
I also looked at the Recast navigation mesh project on github for inspiration (I want to implement something myself and understand it completely), but even though it seems straightforward and isn't too clever with c++ features, I still find it difficult to understand, unfortunately.