Hey everyone! Has anyone worked with tiles (each tile 1x1 in dimensions) and some pathfinding? I’ve managed to make a system for finding route between two points on my roads but the problem is pathfinding script normally doesn’t take into consideration turns between tiles so it will return two points that are separated diagonally (if that makes any sense). You can see how it looks below:
So I have to somehow get the point between that 2nd and 3rd point. Does anyone maybe know how to achieve this? I’ve tried everything and I can’t seem to think of anything
Im currency experimenting with something similar How did you implement your navigation if you don’t mind me asking, mine is horrible , i tried to add some type of penalty sys to force a path
In your pathfinder check if going diagnol is valid. If it isnt then remove that node thats diagnol from the open list.
To check if you can go diagnol you will need to check each corner node has a node to the side and above or below, if either are not accesible then diagnols not an option.
It appears that your A* code is considering diagonals as valid moves. You just need to change it so it only considers the 4 orthogonal neighbors instead.
Well, I’ll try to remove diagonals from searching for the shortest path but this might get tricky because implementation of the algorithm I’m using uses Heap for optimization so I might have some more work to do.
Hmm, I haven’t heard of BFS and how it works. Is it efficient enough for a game with tiles like A*?
True, I’ve just managed to do it like a minute ago haha
Thank you all so much for your help!
The next thing now is to make a Bezier curve (Never worked with them before so I’m scared a bit lol) in those turns so the vehicle doesn’t move like jagged or something
You don’t necessarily need Bezier curves just to smooth the path a bit. A common trick is to have an invisible object following the path exactly, a short distance ahead of your actual vehicle… and then your vehicle always turns directly towards that object and chases it. So, while the invisible object (aka “rabbit”) makes a sharp 90° turn, the chaser rounds off the corner as it follows.
Hmm this is interesting. Since I’m having a lot of different turns on my road tiles, I think making one bezier curve for turning would be kinda easier method.
Note true… considering that with bezier curves you don’t actually pass through the control points (aside from the start and end), and as your N-dimensional bezier increases, your control points end up farther off mark.
You could instead use a quadratic bezier spline, where it’s a series of quadratic beziers. But then you’re going to have to create control points for every 2 control points.
Or you could only create a quadratic bezier at each ‘turn’, using the node of the turn as the control point for the quadratic bezier… but then you’ll need an algorithm to determine where the turns are!
Where as with the method JoeStrout mentions… you effectively get what feels like a quadratic bezier spline, without having to set up a spline in the first place. (and is how many smoothing algorithms work, where you average a current tangent with the tangent of a point in front of you)
Note, you won’t actually have an object in front, it’s just that when you get the ‘next point’ to move towards when pathing, you use a point ever so slightly in front of the agent, and turn towards that. For a car, this will actually look natural… since it’s how people usually drive anyways… you usually drive towards a point you look at in front of yourself.
Well, I managed to find which nodes are for turning and I tried to calculate bezier curve out of those nodes. The problem right now is it’s tricky to calculate when to stop following bezier and some other stuff.
So if I got this right: I spawn my car like I did before but I calculate a point in front of it and the car is always facing that point.
When you’re pathing… instead of getting the next target point using the current position, use a position IN FRONT OF the agent. Just grab a point some scalable distance in front of the agent.
var curPos = agent.position + agent.forward * scale;
I mean… the specifics really depend on how you move your object down the path. But all it really boils down to is moving ‘toward’ a target, rather than ‘to’ a target.
Got it. One question though: How will path of my car be smoothed out? I mean if the car gets right in the middle of the turn, wouldn’t the curPos just get out of the turn?
If I had an empty object that passed the turn already, I can imagine how the car would move towards it in the turn so it wouldn’t go in the straight lines.
@Dominik523 , great job with the sketches — they really make it easier to see what you’re doing!
In your last sketch, the mistake is that your rabbit (the green dot) has gone off the path. You’re calculating it as “a certain distance out in front of the car,” but that’s not correct. It should be “a certain distance ahead of the car on the path.”
Conceptually, take whatever code you’re already using to follow the result of the A* path, just like in your first post… but instead of putting the car there, treat that point as the target (the rabbit). And now, have your car turn towards that point and move forward. When the car gets too close to the target, advance the target a bit further down the path (still using the A* result).
The car isn’t actually following the A* path at all… it’s following the rabbit, and the rabbit is following the A* path.
I’m doing this right now:
position = new Vector3(path[currentPointIndex].x, 0, path[currentPointIndex].y); // next point in the path
target = Vector3.MoveTowards(transform.position, pos, Time.deltaTime * speed);
if(pos == transform.position)
// increase the index and other stuff
…
Oh, I think I got it now. It would look like this:
So it would go like this:
position = new Vector3(path[currentPointIndex].x, 0, path[currentPointIndex].y); // next point in the path
target = Vector3.MoveTowards(transform.position, pos, Time.deltaTime * speed);
rabbitPosition = target;
// getting direction from car to rabbit and adding some speed to it
transform.position = transform.position + (rabbitPosition - transform.position) * time.deltaTime * speed;
So this would make a vector pointing from the car to rabbitPoint, and multiply it by some value in case it’s too small and just add that vector to the transform.position. Gonna try to make this today.
Just wanted to say one more thing: thank you guys sooo much for helping me. This solution is so clever and easy to implement instead of bezier curves and whatnot.
I’m so happy this community has such nice people that are willing to help.
