0
\$\begingroup\$

I would like to move an object through a path found by A* star but taking into account the object's turn radius and movement speed, while also avoiding possible obstacles during a curve. After some research, I found this article in gamasutra about realistic turns and this question. If I understood correctly, to add smooth turns I just need to create a circle in either the left side of the object or the right (depending on which direction it will rotate) and then move the object along that circle until it reach the point in which it can move straight to the goal. I implemented the code from the article, however I couldn't get it working

  • The tank is the object I want to move and the boxes are obstacles;
  • The red Xs are the "waypoints" and the blue line is the line segment between those points;
  • The white circle is the tank's turning radius;
  • The green line is the actual movement the tank would perform taking its turning radius and movement speed into account;
  • And the pink dotted circle represents the "point to leave the circle and start on the straight line" that I've got with the algorithm;

https://i.imgur.com/XKVmOEn.png

The first problem is that I'm not sure how to calculate the right place for the pink circle. If I understood correctly, it should be positioned between the end of the green line's curve and the start of the straight one.

The second problem is that, once solved the first, I don't know how to actually move the tank through the "circular" path, while in straight path I could simply take the direction between the current point and the next, and move along that.

Here's my implementation in gdscript

extends Node2D

var speed = 80
var rotation_speed = 1

var goal = null
var velocity = Vector2()


func _ready():
    goal = get_parent().get_node("Goal").global_position
    

func _physics_process(delta):
    if goal == null:
        return
    
    var pos = global_position
    var circle_radius = speed / rotation_speed
    
    var angle_to_circle_center = rotation + PI/2 #rotation - PI/2
    var circle_pos = pos
    circle_pos.x += circle_radius * cos(angle_to_circle_center)
    circle_pos.y += circle_radius * sin(angle_to_circle_center)
    
    var dx = goal.x - circle_pos.x
    var dy = goal.y - circle_pos.y
    var h = sqrt(dx*dx + dy*dy)
    var r = circle_radius
    
    if h < r:
        return
        
    var d = sqrt(h*h - r*r)
    var theta = acos(r / h)
    
    var phi = atan(dy / dx)
    var Q = Vector2()
    Q.x = circle_pos.x + r * cos(phi + theta)
    Q.y = circle_pos.y + r * sin(phi + theta)
    
    get_parent().get_node("icon").global_position = Q

Any insight would be appreciated - thanks in advance!

\$\endgroup\$
5
  • \$\begingroup\$ How did you generate the red X waypoints? \$\endgroup\$ – Pikalek Jan 1 at 16:19
  • \$\begingroup\$ Also, Pinter's source code is still available. While it's likely to be very out of date for modern C++, it's still pretty useful in terms of a computational example of how to work out the problem. I referenced it when building a non-grid based variant for an old project. \$\endgroup\$ – Pikalek Jan 1 at 16:23
  • \$\begingroup\$ I generated the path using a simple A* pathfinding algorithm in a square grid. Do you mean Marco Pinter? If so, the above code is an implementation of the "Toward More Realistic Pathfinding" article made by him. If you are referring to something else, could you send me the link to that source? \$\endgroup\$ – Ainsley Harriott Jan 1 at 18:23
  • \$\begingroup\$ Yes, I was referring to the article / code by Marco Pinter. While you could apply the smooth turning described on pg 3 of the article, using it with a regular A* might not give you the expected result. Pinter combines the smooth turn calculations with what he refers to as a directional-24 search. The article is about adding turning radius awareness to path finding - that's not quite the same thing as attempting to follow go through a series of waypoints using turning radius constraints. \$\endgroup\$ – Pikalek Jan 1 at 20:37
  • \$\begingroup\$ If you are just focused on calculating the positions where the tank would change from turning to straight travel (I think Pinter's code refers to them as 'touch points'), I can try to answer that. But adding smooth turning to a path from an A* that didn't account for turning radius won't necessarily give the results discussed in the article. \$\endgroup\$ – Pikalek Jan 1 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.