Hello, I need to make a pretty complex calculation to check if someone should be able to hit someone else in a grid multi heigh whit cover environment and am not totally sure what should be the best way to do it
Right now my main plan would be to take my A*pathFinding algorithm and set him in a way he can’t look back, so that he will try to find the shortest way to a target and if that way don’t exist he would return me a false, but am kinda wondering if that would really work. There are many factors like cover, height, target size to consider, and am not totally sure it would work even whit heavy modification on it.
The simple ray is not an option as the game is client/server and you can’t trust the client and I can’t build the 3D environment on the server.
So yeah, am open to suggestion I’ll probably try the pimped A*Pathfinding but I kinda hope there is better solution x)
Well even if i physicly can, that aint a optimise way to do it, and well every map have like 150-200 obstacle per map and would have like 1000 map at the time.
Sorry I made a few assumptions. I thought you were just trying to figure out is someone/something could hit someone/something else in a straight line, assuming you meant shoot a projectile. Obviously you would not need to have an infinitely long ray, it could depend on the range of the weapon, but I’m still assuming we’re shooting here
If you don’t think you can shoot a ray (which btw is optimized in the sense that it’s been around for ages in graphics development and in jme) how long do you think calculating astar pathfinding for 1000 whatevers will take?
I’m still just making assumptions so feel free to correct me here on what you’re actually trying to do.
Yes, I guess I should be more precise xD The map is built in a grid way, meaning you its like a 30 per 30 right now so yeah, you ain’t going pass in 1000 grid something like max 100 if the map became a 100 per 100.
My biggest problem come from angle I guess, that’s where I fear it won’t work. cause of diagonal, a problem you don’t have whit ray.
You still have not specified what being able hit someone means in your context. I gather its somehow restricted to the nearest approximation of a straight line on your grid. What is it, if it is not a projectile?
About running thousand maps at once, at first you need to be able to do whatever you want to do on one map. Later you can try out a thousand maps. Most likely a lot of things will break when you do this.
In Aleron we use Dijkstra to find all tiles a character can move to or attack this turn. To calculate the path to a given target we use A*. But we only use height differences to restrict movement, not ranged skills.
If you are just trying to see if the straight line to an object is ‘visible’ from some other object then any form of graph traversal is a waste of time as it will try hundreds of options that make no sense.
Walk the grid in a straight line. Check for obstacles in each of those grid cells that you intersect. Basically, cast a ray into your grid and check any grid cells that the ray intersects.
You will obviously need enough information on the server if you need to do this calculation on the server. It doesn’t need to be the actual JME scene but it does need to have enough information to walk the grid and check for obstacles. How else would it do it without that info? A graph traversal doesn’t help you if you don’t have the obstacle information.
Yeah the more question I get, the more I realise I might not have been clear enough.
To be able to hit someone mean the path is clear, there is not fully
occupy tile in the way between you and the target. The height should also be considered: you can hit a target that is higher then you, but not if its place in a way that a straight line can’t be drawn between the two characters (in other words, if he is not near the ledge or you ain’t far enough from it, case well, angle and stuff x)
That’s not how I love to see it. I would not plan my production in a way I know it won’t work after scaling, It would simply be a waste of time that some planification would avoid. In the same idea I am not planning my client the same way am planning my server: I allow myself some bad code on my client because I know it would just be run a few times, but I try to keep the server part code as optimise as I can so it would mean less work later and more client on my server.
That’s exactly what I want to do: cast a ray without physically casting it. I have all the info for each of my tiles, and I can tell if they are fully occupied, mildly occupy or empty, but the problem is I don’t know how get all those tiles that are in the path of my target. Then I also have some range and angles to consider, but first I need that line, then I should be able to handle everything else. But I look for a graph traversal tho, because it sound like what I need, as the server have all the info about the position in a 2D grid. Also, as I will need to present all the targeteble tile on the client side i will need something to decide if those tile are available or not, all of those in range
Anyway here is a pic to explain whit my superbe paint skills x) :
I think its an good idea to explain what you want to do first in this case, like, what its ?
An cannon that will aim for the closest target or something ?
I am almost sure you are going for the wrong approach with rays…
Easy way, pick a step size small enough to catch the corners you want to catch… ignore the cell if it’s the same as the cell you just checked.
pos += delta;
check cell
Harder way, step along x and step along y to find the axis intersections. Pick the next closest one, then the next closest one, etc. I suspect that since you hadn’t immediately jumped to this method that it might be more complicated math than you are ready to deal with right now.
My advice, go with the first approach. Pick a step size 1/10th of your cell size or so.
delta = target.subtract(pos).normalize().mult(0.1)
Edit: and note: if your first reaction to the simple suggestion is “but that will be too slow” then just remember you were willing to traverse your whole graph out in all directions just to find one direction before. The “is cell different than last cell” check should be very fast and you can tweak the step size to balance performance with ‘corner cutting’.
That’s why I kinda did not love the idea and came here But yeah, I see what you mean by the axis and delta, look pretty fesable and efficent enough, though I think I will think this problem a bit longer and try to see if I can’t do something else.
I ain’t in a hurry for it x) Its more like a problem I love to think about when I have free time, it’s fun to try some algorithm between the simple yet long Client/server packet programming, and usual industrial programmation x)
For the moment am thinking about doing what you say, but force the chicken instead of doing bit by bit by directly check the beginning and ending at each height. If they ain’t the same you take both of them in the should check if available tile list. Play between int and float so it will only consider the entire part of the number in term of coordonate and yet letting the pytagore part been consider in float.
It give something like that, but starting for the middle of the tile.
In the end tho i would love to produce something like they have :
Been able to scan the whole map to show what can be target and what can’t be target. But i have a feeling that one aint gona be easy to do right x)
Something like that is what I use for Mythruna ray casting only in 3D.
But given your picture:
Essentially you figure out how far you need to step in the x axis to go one step in y. And how far you need to step in the y axis to go one step in x. Keep track of the distance to the next step in each of those trackers and use the closest one. Detect only leading edges and then you will always know which cell you are hitting.
So in your example, the y-axis intersector first hits cell 3,2 and it’s the closest (because it’s the only hit). Then the x-axis intersector hits cell 3,3 which is closer than the next y-axis intersector of 4, 3… and so on.
You do that to account for the cases where angles are very narrow and so you will hit say the y-planes several times before crossing another x plane.
As to your example, if everything is grid locked then they don’t even need to do anything more advanced than that for sure. For a simple 2D grid, you can even precalculate the cell-to-cell dependencies and order them from the center out. So if you find that the +2, -1 relative cell is solid then you can immediately mark a whole bunch of cells as blocked. Given that the range is limited this isn’t even a very big table.
I’ll probably try the pimped A*Pathfinding but I kinda hope there is better solution x)
The “is cell different than last cell” check should be very fast and you can tweak the step size to balance performance with ‘corner cutting’.
