🔒 Locked

Linear Programming

Started by Greg K Apr 29, 2004 at 1:42 PM 2 replies 400+ views

Original Post

Apr 29, 2004 at 1:42 PM

I am currently working on an A* implementation using quad trees http://gamedev.net/community/forums/topic.asp?topic_id=220725 and need some help with optimizing the path after I have used the A* algorithm. Basically what I have is a list of x,y constraints and I want to minimize the distance. Timkin suggested that I look into Linear Programming / Linear Constraint Satisfaction. I looked them up on google and there was a lot of information. Basically I got to the point where I could represent my problem in a set of linear equations but I don''t know where to go from there. D= sqrt(pow((x2-x1),2)+pow((y2-y1),2))...sqrt(pow((x(n)-x(n-1)),2)+pow((y(n)-y(n-1)),2)) and then a list of the vertices in which one point is fixed and the other varies between two numbers eg: x1 = 4 5 <= y1 <= 12 ... But what do I do now? Is this a case in which I would use Simplex? I took a look at that but it didn''t seem to fit the bill. Maybe I just didn''t understand it. -Greg

SiCrane

Mod

473

SiCrane

Apr 29, 2004 at 2:17 PM

A Nelder-Mead approach seems appropriate here. You can remap the constraints into a unit n-cube that the simplex oozes along if that would help you understand the process better. (I know "ooze" is not the technical term for it, but my mental image of the simplex method is an n-dimensional amoeba oozing along the problem space.)

Greg K

Author

Greg K

Apr 29, 2004 at 2:46 PM

I will look into the books suggested. I am looking to smooth the path within the nodes though, not the smoothing that I have seen on the net where it only gets rid of the ''ugly'' effects of A*.
-Greg

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.