So I know i already posted, but i forgot to mention one important detail.
We were running into problems with the pathfinding, where a physics object could land in the graph on any orientation/position. The question was, How could we find out the outter edges of the object and how they related to the graph, so that we could tell the pathfinder to block them off.
We came up with a solution and its pretty spiffy if you ask me. So after coming up with some crazy ideas that involved pathfinding from vertex to vertex on the object we figured (thanks Josh) that our problem was the same problem as rendering a line in pixels.
The problem there is that what if you want to draw a line that is thinner than a pixel? You would have to figure out what pixels should be coloured by the line.
Our problem was the same. We had the verticies of the object (ends of the line) and wanted to know what blocks in the graph(pixels) would need to be blocked off so the A.I. walks around them.
Turns out the computer graphics industry has been doing this for 20+ years with an algorthim called "Bresenham's Line Algorithm" and it does exactly what we need.
Yay.
Monday, February 9, 2009
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment