I would really appreciate it if anyone could help me with what’s going on in this code, please…
It is something I’m trying to convert from C for the code exchange, but somewhere in the middle of this listing the values appear to change from what’s in the table to negative values and I just can’t figure out why!
The problem occurs in the ‘calcDist’ function called at line 217…
main.lua:
[lua]-- particle room draw
– http://alienryderflex.com/shortest_path/
– turn off status display bar
display.setStatusBar(display.HiddenStatusBar)
– groups
local background, fill, outline, dottop, dostop = display.newGroup(), display.newGroup(), display.newGroup(), display.newGroup(), display.newGroup()
– background
display.newRect(background, 0,0,display.contentWidth,display.contentHeight):setFillColor(30,30,60)
– path start/end points
local startpath, endpath = nil, nil
function findPath(startpath,endpath,polys)
local path = display.newGroup()
print()
print(‘start’,startpath.x,startpath.y)
print(‘end’,endpath.x,endpath.y)
print()
for p=1, #polys do
print('poly '…p)
local poly = polys[p]
for i=1, #poly do
print(poly[i].x,poly[i].y)
end
print()
end
print()
function calcDist( sX, sY, eX, eY )
eX = eX - sX
eY = eY - sY
print(‘LINE’,sX,sY,eX,eY)
local l = display.newLine(sX,sY,eX,eY)
l.width=2
l:setColor(200,200,200)
return math.sqrt( eX * eX + eY * eY )
end
function pointInPolygonSet( testX, testY, allPolys )
local oddNodes = false – bool
local polyI, i, j – int
for polyI=1, #allPolys do
local poly = allPolys[polyI]
for i=1, #poly do
j = i + 1
if (j >= #poly) then
j = 1
end
– print(#poly, tostring(i), tostring(j), tostring(testY), tostring(poly[i]), tostring(poly[j]))
– print(tostring(poly[i].y), tostring(poly[j].y))
if (poly[i].y < testY and poly[j].y >= testY or poly[j].y < testY and poly[i].y >= testY) then
if (poly[i].x + (testY-poly[i].y) / (poly[j].y-poly[i].y) * (poly[j].x-poly[i].x) < testX) then
oddNodes = not oddNodes
end
end
end
end
return oddNodes
end
–[[
// This function should be called with the full set of *all* relevant polygons.
// (The algorithm automatically knows that enclosed polygons are ìno-goî
// areas.)
//
// Note: As much as possible, this algorithm tries to return YES when the
// test line-segment is exactly on the border of the polygon, particularly
// if the test line-segment *is* a side of a polygon.
]]–
function lineInPolygonSet( testSX, testSY, testEX, testEY, allPolys )
local theCos, theSin, dist, sX, sY, eX, eY, rotSX, rotSY, rotEX, rotEY, crossX
local i, j, polyI
testEX = testEX - testSX
testEY = testEY - testSY
dist = math.sqrt( testEX * testEX + testEY * testEY )
theCos = testEX / dist
theSin = testEY / dist
for polyI=1, #allPolys do
local poly = allPolys[polyI]
for i=1, #poly do
j = i + 1
if (j >= #poly) then
j = 1
end
sX = poly[i].x - testSX
sY = poly[i].y - testSY
eX = poly[j].x - testSX
eY = poly[j].y - testSY
if (sX == 0 and sY == 0 and eX == testEX and eY == testEY or eX == 0 and eY == 0 and sX == testEX and sY == testEY) then
return true
end
rotSX = sX * theCos + sY * theSin
rotSY = sY * theCos - sX * theSin
rotEX = eX * theCos + eY * theSin
rotEY = eY * theCos - eX * theSin
if (rotSY < 0 and rotEY > 0 or rotEY < 0 and rotSY > 0) then
crossX = rotSX + (rotEX-rotSX)*(0-rotSY)/(rotEY-rotSY)
if (crossX >= 0 and crossX <= dist) then
return false
end
end
if (rotSY == 0 and rotEY == 0 and (rotSX >= 0 or rotEX >= 0) and (rotSX <= dist or rotEX <= dist)
and (rotSX < 0 or rotEX < 0 or rotSX > dist or rotEX > dist)) then
return false
end
end
end
return pointInPolygonSet( testSX + testEX / 2, testSY + testEY / 2, allPolys )
end
–[[
function swapPoints(point *a, point *b)
point swap=*a
*a=*b
*b=swap
end
]]–
–[[
// Finds the shortest path from sX,sY to eX,eY that stays within the polygon set.
//
// Note: To be safe, the solutionX and solutionY arrays should be large enough
// to accommodate all the corners of your polygon set (although it is
// unlikely that anywhere near that many elements will ever be needed).
//
// Returns YES if the optimal solution was found, or NO if there is no solution.
// If a solution was found, solutionX and solutionY will contain the coordinates
// of the intermediate nodes of the path, in order. (The startpoint and endpoint
// are assumed, and will not be included in the solution.)
]]–
function shortestPath( sX, sY, eX, eY, allPolys ) – , *solutionX, *solutionY )
local solutionNodes, solutions = 0, {}
local INF = 9999999 – (larger than total solution dist could ever be)
local pointList = {} – (enough for all polycorners plus two)
local pointCount
local treeCount, polyI, i, j, bestI, bestJ – int
local bestDist, newDist – double
– Fail if either the startpoint or endpoint is outside the polygon set.
if (not pointInPolygonSet(sX,sY,allPolys) or not pointInPolygonSet(eX,eY,allPolys)) then
print(‘fail’)
return false
end
– If there is a straight-line solution, return with it immediately.
if (lineInPolygonSet(sX,sY,eX,eY,allPolys)) then
solutionNodes = 0
print(‘solutionNodes’,solutionNodes)
return true
end
– Build a point list that refers to the corners of the
– polygons, as well as to the startpoint and endpoint.
pointList[1] = {x=sX,y=sY,totalDist=0}
pointCount=1
for polyI=1, #allPolys do
local poly = allPolys[polyI]
for i=1, #poly do
pointList[#pointList+1] = {x=poly[i].x,y=poly[i].y,totalDist=0}
print(‘point’,pointList[#pointList].x,pointList[#pointList].y)
– pointCount = pointCount + 1
end
end
pointList[#pointList+1] = {x=eX,y=eY,totalDist=0}
– pointCount = pointCount + 1
pointCount = #pointList
for i=1, #pointList do
local c = display.newCircle(pointList[i].x,pointList[i].y,10)
c:setFillColor(0,0,255,150)
print(‘FINAL’,pointList[i].x,pointList[i].y)
end
– Initialize the shortest-path tree to include just the startpoint.
treeCount = 1
pointList[1].totalDist = 0
print(‘start’, pointList[1].totalDist)
– Iteratively grow the shortest-path tree until it reaches the endpoint
– or until it becomes unable to grow, in which case exit with failure.
bestJ = 1
print(‘pointCount’,pointCount)
while (bestJ <= pointCount) do
bestDist = INF
print(‘go’)
for i=1, treeCount do
for i=1, #pointList do
local c = display.newCircle(pointList[i].x,pointList[i].y,10)
c:setFillColor(0,0,255,150)
print(‘SECOND’,pointList[i].x,pointList[i].y)
end
print(i,treeCount,pointCount)
if (treeCount<=pointCount-1) then
for j=treeCount, pointCount-1 do
local lineIn = lineInPolygonSet( pointList[i].x, pointList[i].y, pointList[j].x, pointList[j].y, allPolys)
–print(‘lineIn’,lineIn)
if (lineIn) then
–print(‘calc’,pointList[i].x, pointList[i].y, pointList[j].x, pointList[j].y)
local dist = calcDist( pointList[i].x, pointList[i].y, pointList[j].x, pointList[j].y )
–print(‘dist’,pointList[i].totalDist,dist)
newDist = pointList[i].totalDist + dist
if (newDist < bestDist) then
–print(‘newDist < bestDist’,newDist, bestDist)
bestDist = newDist
bestI = i
bestJ = j
end
end
end
else
print(‘ARGH’,treeCount,pointCount-1)
end
end
print(‘stop’,bestDist,bestJ)
– this IF always enters and appears to show that there is never a solution
–[[if (bestDist == INF) then
print(‘bestDist, INF’, bestDist, INF, bestJ, pointCount)
return false – (no solution)
end]]–
–print(‘bestJ,bestI’,bestJ,bestI)
pointList[bestJ].prev = bestI
pointList[bestJ].totalDist = bestDist
– swapPoints( &pointList[bestJ], &pointList[treeCount] )
local a, b = pointList[bestJ], pointList[treeCount]
pointList[bestJ], pointList[treeCount] = b, a
treeCount = treeCount + 1
end
– Load the solution arrays.
solutionNodes = -1
i = treeCount - 1
while (i > 1) do
i = pointList[i].prev
solutionNodes = solutionNodes + 1
end
j = solutionNodes – - 1
i = treeCount – - 1
print(j,i,solutionNodes,treeCount)
while (j >= 1) do
i = pointList[i].prev
– solutionX[j] = pointList[i].x
– solutionY[j] = pointList[i].y
solutions[#solution+1] = { x=pointList[i].x, y=pointList[i].y }
j = j - 1
end
– Success.
return true, solutions
end
local result, points = shortestPath( startpath.x, startpath.y, endpath.x, endpath.y, polys )
print(result, points)
return result, points
end
local polys = { {} }
function completePoly(event)
local poly = polys[#polys]
poly[#poly+1] = poly[1]
local l = display.newLine(poly[#poly-1].x,poly[#poly-1].y,poly[#poly].x,poly[#poly].y)
l.width=5
event.target:removeEventListener(“tap”,completePoly)
polys[#polys+1] = {}
return true
end
function tap(event)
local poly = polys[#polys]
poly[#poly+1] = event
if (#poly == 1) then
local circle = display.newCircle(event.x,event.y,15)
circle:addEventListener(“tap”,completePoly)
end
if (#poly>1) then
local l = display.newLine(poly[#poly-1].x,poly[#poly-1].y,poly[#poly].x,poly[#poly].y)
l.width=5
end
return true
end
Runtime:addEventListener(“tap”,tap)
function getStartEnd(event)
local c = display.newCircle(event.x,event.y,15)
if (startpath == nil) then
startpath = event
c:setFillColor(0,255,0)
else
endpath = event
c:setFillColor(255,0,0)
table.remove(polys,#polys)
local result, path = findPath(startpath,endpath,polys)
end
return true
end
local stopit = display.newCircle(dostop,50,50,25)
function dostoptap(event)
stopit:setFillColor(0,0,255)
Runtime:removeEventListener(“tap”,tap)
Runtime:addEventListener(“tap”,getStartEnd)
return true
end
dostop:addEventListener(“tap”,dostoptap)[/lua] [import]uid: 8271 topic_id: 24492 reply_id: 324492[/import]
[import]uid: 8271 topic_id: 24492 reply_id: 101222[/import]
