diff options
Diffstat (limited to 'src/control/PathFind.cpp')
-rw-r--r-- | src/control/PathFind.cpp | 352 |
1 files changed, 192 insertions, 160 deletions
diff --git a/src/control/PathFind.cpp b/src/control/PathFind.cpp index 44062b38..ee15b82f 100644 --- a/src/control/PathFind.cpp +++ b/src/control/PathFind.cpp @@ -17,12 +17,19 @@ CPathFind ThePaths; #define MAX_DIST INT16_MAX-1 #define MIN_PED_ROUTE_DISTANCE 23.8f + +#define NUMTEMPNODES 4000 +#define NUMDETACHED_CARS 100 +#define NUMDETACHED_PEDS 50 + + // object flags: // 1 UseInRoadBlock // 2 east/west road(?) CPathInfoForObject *InfoForTileCars; CPathInfoForObject *InfoForTilePeds; + // unused CTempDetachedNode *DetachedNodesCars; CTempDetachedNode *DetachedNodesPeds; @@ -243,6 +250,7 @@ CPathFind::AllocatePathFindInfoMem(int16 numPathGroups) delete[] InfoForTilePeds; InfoForTilePeds = nil; + // NB: MIAMI doesn't use numPathGroups here but hardcodes 4500 InfoForTileCars = new CPathInfoForObject[12*numPathGroups]; memset(InfoForTileCars, 0, 12*numPathGroups*sizeof(CPathInfoForObject)); InfoForTilePeds = new CPathInfoForObject[12*numPathGroups]; @@ -253,10 +261,10 @@ CPathFind::AllocatePathFindInfoMem(int16 numPathGroups) DetachedNodesCars = nil; delete[] DetachedNodesPeds; DetachedNodesPeds = nil; - DetachedNodesCars = new CTempDetachedNode[100]; - memset(DetachedNodesCars, 0, 100*sizeof(CTempDetachedNode)); - DetachedNodesPeds = new CTempDetachedNode[50]; - memset(DetachedNodesPeds, 0, 50*sizeof(CTempDetachedNode)); + DetachedNodesCars = new CTempDetachedNode[NUMDETACHED_CARS]; + memset(DetachedNodesCars, 0, NUMDETACHED_CARS*sizeof(CTempDetachedNode)); + DetachedNodesPeds = new CTempDetachedNode[NUMDETACHED_PEDS]; + memset(DetachedNodesPeds, 0, NUMDETACHED_PEDS*sizeof(CTempDetachedNode)); } void @@ -306,6 +314,7 @@ CPathFind::StoreNodeInfoCar(int16 id, int16 node, int8 type, int8 next, int16 x, InfoForTileCars[i].numLeftLanes = numLeft; InfoForTileCars[i].numRightLanes = numRight; + if(type) for(i = 0; i < node; i++){ j = id*12 + i; @@ -346,10 +355,12 @@ CPathFind::PreparePathData(void) printf("PreparePathData\n"); if(!CPathFind::LoadPathFindData() && // empty InfoForTileCars && InfoForTilePeds && - DetachedNodesCars && DetachedNodesPeds){ - tempNodes = new CTempNode[4000]; + DetachedNodesCars && DetachedNodesPeds + ){ + tempNodes = new CTempNode[NUMTEMPNODES]; m_numConnections = 0; + for(i = 0; i < PATHNODESIZE; i++) m_pathNodes[i].unkBits = 0; @@ -369,6 +380,7 @@ CPathFind::PreparePathData(void) for(i = 0; i < PATHNODESIZE; i++) for(j = 0; j < 12; j++) if(InfoForTileCars[i*12 + j].type == NodeTypeExtern){ + // MIAMI has MI:%d here but no argument for it if(InfoForTileCars[i*12 + j].numLeftLanes < 0) printf("ILLEGAL BLOCK. NEGATIVE NUMBER OF LANES (Obj:%d)\n", i); if(InfoForTileCars[i*12 + j].numRightLanes < 0) @@ -378,9 +390,9 @@ CPathFind::PreparePathData(void) } m_numPathNodes = 0; - PreparePathDataForType(PATH_CAR, tempNodes, InfoForTileCars, 1.0f, DetachedNodesCars, 100); + PreparePathDataForType(PATH_CAR, tempNodes, InfoForTileCars, 1.0f, DetachedNodesCars, NUMDETACHED_CARS); m_numCarPathNodes = m_numPathNodes; - PreparePathDataForType(PATH_PED, tempNodes, InfoForTilePeds, 1.0f, DetachedNodesPeds, 50); + PreparePathDataForType(PATH_PED, tempNodes, InfoForTilePeds, 1.0f, DetachedNodesPeds, NUMDETACHED_PEDS); m_numPedPathNodes = m_numPathNodes - m_numCarPathNodes; // TODO: figure out what exactly is going on here @@ -431,6 +443,7 @@ CPathFind::PreparePathData(void) InfoForTileCars = nil; delete[] InfoForTilePeds; InfoForTilePeds = nil; + delete[] DetachedNodesCars; DetachedNodesCars = nil; delete[] DetachedNodesPeds; @@ -476,29 +489,28 @@ CPathFind::CountFloodFillGroups(uint8 type) break; node = &m_pathNodes[i]; - node->next = nil; + node->SetNext(nil); node->group = n; if(node->numLinks == 0){ if(type == PATH_CAR) printf("Single car node: %f %f %f (%d)\n", - node->pos.x, node->pos.y, node->pos.z, - m_mapObjects[node->objectIndex]->m_modelIndex); + node->GetX(), node->GetY(), node->GetZ(), m_mapObjects[node->objectIndex]->GetModelIndex()); else printf("Single ped node: %f %f %f\n", - node->pos.x, node->pos.y, node->pos.z); + node->GetX(), node->GetY(), node->GetZ()); } while(node){ prev = node; - node = node->next; + node = node->GetNext(); for(i = 0; i < prev->numLinks; i++){ - l = m_connections[prev->firstLink + i]; + l = ConnectedNode(prev->firstLink + i); if(m_pathNodes[l].group == 0){ m_pathNodes[l].group = n; if(m_pathNodes[l].group == 0) m_pathNodes[l].group = INT8_MIN; - m_pathNodes[l].next = node; + m_pathNodes[l].SetNext(node); node = &m_pathNodes[l]; } } @@ -513,7 +525,7 @@ int32 TempListLength; void CPathFind::PreparePathDataForType(uint8 type, CTempNode *tempnodes, CPathInfoForObject *objectpathinfo, - float maxdist, CTempDetachedNode *detachednodes, int unused) + float maxdist, CTempDetachedNode *detachednodes, int numDetached) { static CVector CoorsXFormed; int i, j, k, l; @@ -525,14 +537,16 @@ CPathFind::PreparePathDataForType(uint8 type, CTempNode *tempnodes, CPathInfoFor int nearestId; int next; int oldNumPathNodes, oldNumLinks; - CVector dist; + float dist; int iseg, jseg; int istart, jstart; int done, cont; + int tileStart; oldNumPathNodes = m_numPathNodes; oldNumLinks = m_numConnections; +#define OBJECTINDEX(n) (m_pathNodes[(n)].objectIndex) // Initialize map objects for(i = 0; i < m_numMapObjects; i++) for(j = 0; j < 12; j++) @@ -540,28 +554,30 @@ CPathFind::PreparePathDataForType(uint8 type, CTempNode *tempnodes, CPathInfoFor // Calculate internal nodes, store them and connect them to defining object for(i = 0; i < m_numMapObjects; i++){ - start = 12*m_mapObjects[i]->m_modelIndex; + tileStart = m_numPathNodes; + start = 12 * m_mapObjects[i]->GetModelIndex(); for(j = 0; j < 12; j++){ - if(objectpathinfo[start + j].type != NodeTypeIntern) - continue; - CalcNodeCoors( - objectpathinfo[start + j].x, - objectpathinfo[start + j].y, - objectpathinfo[start + j].z, - i, - &CoorsXFormed); - m_pathNodes[m_numPathNodes].pos = CoorsXFormed; - m_pathNodes[m_numPathNodes].objectIndex = i; - m_pathNodes[m_numPathNodes].unkBits = 1; - m_mapObjects[i]->m_nodeIndices[type][j] = m_numPathNodes++; + if(objectpathinfo[start + j].type == NodeTypeIntern){ + CalcNodeCoors( + objectpathinfo[start + j].x, + objectpathinfo[start + j].y, + objectpathinfo[start + j].z, + i, + &CoorsXFormed); + m_pathNodes[m_numPathNodes].SetPosition(CoorsXFormed); + OBJECTINDEX(m_numPathNodes) = i; + m_pathNodes[m_numPathNodes].unkBits = 1; + m_mapObjects[i]->m_nodeIndices[type][j] = m_numPathNodes; + m_numPathNodes++; + } } } + // Insert external nodes into TempList TempListLength = 0; for(i = 0; i < m_numMapObjects; i++){ - start = 12*m_mapObjects[i]->m_modelIndex; - + start = 12 * m_mapObjects[i]->GetModelIndex(); for(j = 0; j < 12; j++){ if(objectpathinfo[start + j].type != NodeTypeExtern) continue; @@ -618,8 +634,8 @@ CPathFind::PreparePathDataForType(uint8 type, CTempNode *tempnodes, CPathInfoFor tempnodes[nearestId].linkState = 2; // collapse this node with nearest we found - dx = m_pathNodes[tempnodes[nearestId].link1].pos.x - m_pathNodes[tempnodes[nearestId].link2].pos.x; - dy = m_pathNodes[tempnodes[nearestId].link1].pos.y - m_pathNodes[tempnodes[nearestId].link2].pos.y; + dx = m_pathNodes[tempnodes[nearestId].link1].GetX() - m_pathNodes[tempnodes[nearestId].link2].GetX(); + dy = m_pathNodes[tempnodes[nearestId].link1].GetY() - m_pathNodes[tempnodes[nearestId].link2].GetY(); tempnodes[nearestId].pos = (tempnodes[nearestId].pos + CoorsXFormed)*0.5f; mag = Sqrt(dx*dx + dy*dy); tempnodes[nearestId].dirX = dx/mag; @@ -648,6 +664,7 @@ CPathFind::PreparePathDataForType(uint8 type, CTempNode *tempnodes, CPathInfoFor continue; // Add link to other side of the external + // NB this clears the flags in MIAMI if(tempnodes[j].link1 == i) m_connections[m_numConnections] = tempnodes[j].link2; else if(tempnodes[j].link2 == i) @@ -655,8 +672,8 @@ CPathFind::PreparePathDataForType(uint8 type, CTempNode *tempnodes, CPathInfoFor else continue; - dist = m_pathNodes[i].pos - m_pathNodes[m_connections[m_numConnections]].pos; - m_distances[m_numConnections] = dist.Magnitude(); + dist = (m_pathNodes[i].GetPosition() - m_pathNodes[ConnectedNode(m_numConnections)].GetPosition()).Magnitude(); + m_distances[m_numConnections] = dist; m_connectionFlags[m_numConnections].flags = 0; if(type == PATH_CAR){ @@ -681,6 +698,7 @@ CPathFind::PreparePathDataForType(uint8 type, CTempNode *tempnodes, CPathInfoFor m_carPathLinks[m_numCarPathLinks].numLeftLanes = tempnodes[j].numLeftLanes; m_carPathLinks[m_numCarPathLinks].numRightLanes = tempnodes[j].numRightLanes; m_carPathLinks[m_numCarPathLinks].trafficLightType = 0; + assert(m_numCarPathLinks <= NUM_CARPATHLINKS); m_carPathConnections[m_numConnections] = m_numCarPathLinks++; } } @@ -689,33 +707,35 @@ CPathFind::PreparePathDataForType(uint8 type, CTempNode *tempnodes, CPathInfoFor m_numConnections++; } + // Find i inside path segment iseg = 0; for(j = Max(oldNumPathNodes, i-12); j < i; j++) - if(m_pathNodes[j].objectIndex == m_pathNodes[i].objectIndex) + if(OBJECTINDEX(j) == OBJECTINDEX(i)) iseg++; - istart = 12*m_mapObjects[m_pathNodes[i].objectIndex]->m_modelIndex; + istart = 12 * m_mapObjects[m_pathNodes[i].objectIndex]->GetModelIndex(); // Add links to other internal nodes for(j = Max(oldNumPathNodes, i-12); j < Min(m_numPathNodes, i+12); j++){ - if(m_pathNodes[i].objectIndex != m_pathNodes[j].objectIndex || i == j) + if(OBJECTINDEX(i) != OBJECTINDEX(j) || i == j) continue; // N.B.: in every path segment, the externals have to be at the end jseg = j-i + iseg; - jstart = 12*m_mapObjects[m_pathNodes[j].objectIndex]->m_modelIndex; + jstart = 12 * m_mapObjects[m_pathNodes[j].objectIndex]->GetModelIndex(); if(objectpathinfo[istart + iseg].next == jseg || objectpathinfo[jstart + jseg].next == iseg){ - // Found a link between i and j + // Found a link between i and jConnectionSetCrossesRoad + // NB this clears the flags in MIAMI m_connections[m_numConnections] = j; - dist = m_pathNodes[i].pos - m_pathNodes[j].pos; - m_distances[m_numConnections] = dist.Magnitude(); + dist = (m_pathNodes[i].GetPosition() - m_pathNodes[j].GetPosition()).Magnitude(); + m_distances[m_numConnections] = dist; if(type == PATH_CAR){ - posx = (m_pathNodes[i].pos.x + m_pathNodes[j].pos.x)*0.5f; - posy = (m_pathNodes[i].pos.y + m_pathNodes[j].pos.y)*0.5f; - dx = m_pathNodes[j].pos.x - m_pathNodes[i].pos.x; - dy = m_pathNodes[j].pos.y - m_pathNodes[i].pos.y; + posx = (m_pathNodes[i].GetX() + m_pathNodes[j].GetX())*0.5f; + posy = (m_pathNodes[i].GetY() + m_pathNodes[j].GetY())*0.5f; + dx = m_pathNodes[j].GetX() - m_pathNodes[i].GetX(); + dy = m_pathNodes[j].GetY() - m_pathNodes[i].GetY(); mag = Sqrt(dx*dx + dy*dy); dx /= mag; dy /= mag; @@ -744,6 +764,7 @@ CPathFind::PreparePathDataForType(uint8 type, CTempNode *tempnodes, CPathInfoFor m_carPathLinks[m_numCarPathLinks].numLeftLanes = -1; m_carPathLinks[m_numCarPathLinks].numRightLanes = -1; m_carPathLinks[m_numCarPathLinks].trafficLightType = 0; + assert(m_numCarPathLinks <= NUM_CARPATHLINKS); m_carPathConnections[m_numConnections] = m_numCarPathLinks++; } }else{ @@ -825,7 +846,7 @@ CPathFind::PreparePathDataForType(uint8 type, CTempNode *tempnodes, CPathInfoFor if(!m_pathNodes[i].bDeadEnd){ k = 0; for(j = 0; j < m_pathNodes[i].numLinks; j++) - if(!m_pathNodes[m_connections[m_pathNodes[i].firstLink + j]].bDeadEnd) + if(!m_pathNodes[ConnectedNode(m_pathNodes[i].firstLink + j)].bDeadEnd) k++; if(k < 2){ m_pathNodes[i].bDeadEnd = true; @@ -847,9 +868,11 @@ CPathFind::PreparePathDataForType(uint8 type, CTempNode *tempnodes, CPathInfoFor m_pathNodes[j] = m_pathNodes[j+1]; // Fix links - for(j = oldNumLinks; j < m_numConnections; j++) - if(m_connections[j] >= i) - m_connections[j]--; + for(j = oldNumLinks; j < m_numConnections; j++){ + int node = ConnectedNode(j); + if(node >= i) + m_connections[j] = node-1; + } // Also in treadables for(j = 0; j < m_numMapObjects; j++) @@ -875,12 +898,12 @@ CPathFind::CalcRoadDensity(float x, float y) float density = 0.0f; for(i = 0; i < m_numCarPathNodes; i++){ - if(Abs(m_pathNodes[i].pos.x - x) < 80.0f && - Abs(m_pathNodes[i].pos.y - y) < 80.0f && + if(Abs(m_pathNodes[i].GetX() - x) < 80.0f && + Abs(m_pathNodes[i].GetY() - y) < 80.0f && m_pathNodes[i].numLinks > 0){ for(j = 0; j < m_pathNodes[i].numLinks; j++){ - int next = m_connections[m_pathNodes[i].firstLink + j]; - float dist = (m_pathNodes[i].pos - m_pathNodes[next].pos).Magnitude2D(); + int next = ConnectedNode(m_pathNodes[i].firstLink + j); + float dist = (m_pathNodes[i].GetPosition() - m_pathNodes[next].GetPosition()).Magnitude2D(); next = m_carPathConnections[m_pathNodes[i].firstLink + j]; density += m_carPathLinks[next].numLeftLanes * dist; density += m_carPathLinks[next].numRightLanes * dist; @@ -888,11 +911,11 @@ CPathFind::CalcRoadDensity(float x, float y) if(m_carPathLinks[next].numLeftLanes < 0) printf("Link from object %d to %d (MIs)\n", m_mapObjects[m_pathNodes[i].objectIndex]->GetModelIndex(), - m_mapObjects[m_pathNodes[m_connections[m_pathNodes[i].firstLink + j]].objectIndex]->GetModelIndex()); + m_mapObjects[m_pathNodes[ConnectedNode(m_pathNodes[i].firstLink + j)].objectIndex]->GetModelIndex()); if(m_carPathLinks[next].numRightLanes < 0) printf("Link from object %d to %d (MIs)\n", m_mapObjects[m_pathNodes[i].objectIndex]->GetModelIndex(), - m_mapObjects[m_pathNodes[m_connections[m_pathNodes[i].firstLink + j]].objectIndex]->GetModelIndex()); + m_mapObjects[m_pathNodes[ConnectedNode(m_pathNodes[i].firstLink + j)].objectIndex]->GetModelIndex()); } } } @@ -904,8 +927,8 @@ CPathFind::TestForPedTrafficLight(CPathNode *n1, CPathNode *n2) { int i; for(i = 0; i < n1->numLinks; i++) - if(&m_pathNodes[m_connections[n1->firstLink + i]] == n2) - return m_connectionFlags[n1->firstLink + i].bTrafficLight; + if(&m_pathNodes[ConnectedNode(n1->firstLink + i)] == n2) + return ConnectionHasTrafficLight(n1->firstLink + i); return false; } @@ -914,8 +937,8 @@ CPathFind::TestCrossesRoad(CPathNode *n1, CPathNode *n2) { int i; for(i = 0; i < n1->numLinks; i++) - if(&m_pathNodes[m_connections[n1->firstLink + i]] == n2) - return m_connectionFlags[n1->firstLink + i].bCrossesRoad; + if(&m_pathNodes[ConnectedNode(n1->firstLink + i)] == n2) + return ConnectionCrossesRoad(n1->firstLink + i); return false; } @@ -923,20 +946,20 @@ void CPathFind::AddNodeToList(CPathNode *node, int32 listId) { int i = listId & 0x1FF; - node->next = m_searchNodes[i].next; - node->prev = &m_searchNodes[i]; - if(m_searchNodes[i].next) - m_searchNodes[i].next->prev = node; - m_searchNodes[i].next = node; + node->SetNext(m_searchNodes[i].GetNext()); + node->SetPrev(&m_searchNodes[i]); + if(m_searchNodes[i].GetNext()) + m_searchNodes[i].GetNext()->SetPrev(node); + m_searchNodes[i].SetNext(node); node->distance = listId; } void CPathFind::RemoveNodeFromList(CPathNode *node) { - node->prev->next = node->next; - if(node->next) - node->next->prev = node->prev; + node->GetPrev()->SetNext(node->GetNext()); + if(node->GetNext()) + node->GetNext()->SetPrev(node->GetPrev()); } void @@ -945,7 +968,7 @@ CPathFind::RemoveBadStartNode(CVector pos, CPathNode **nodes, int16 *n) int i; if(*n < 2) return; - if(DotProduct2D(nodes[1]->pos - pos, nodes[0]->pos - pos) < 0.0f){ + if(DotProduct2D(nodes[1]->GetPosition() - pos, nodes[0]->GetPosition() - pos) < 0.0f){ (*n)--; for(i = 0; i < *n; i++) nodes[i] = nodes[i+1]; @@ -956,10 +979,12 @@ void CPathFind::SetLinksBridgeLights(float x1, float x2, float y1, float y2, bool enable) { int i; - for(i = 0; i < m_numCarPathLinks; i++) - if(x1 < m_carPathLinks[i].pos.x && m_carPathLinks[i].pos.x < x2 && - y1 < m_carPathLinks[i].pos.y && m_carPathLinks[i].pos.y < y2) + for(i = 0; i < m_numCarPathLinks; i++){ + CVector2D pos = m_carPathLinks[i].GetPosition(); + if(x1 < pos.x && pos.x < x2 && + y1 < pos.y && pos.y < y2) m_carPathLinks[i].bBridgeLights = enable; + } } void @@ -970,7 +995,7 @@ CPathFind::SwitchOffNodeAndNeighbours(int32 nodeId, bool disable) m_pathNodes[nodeId].bDisabled = disable; if(m_pathNodes[nodeId].numLinks < 3) for(i = 0; i < m_pathNodes[nodeId].numLinks; i++){ - next = m_connections[m_pathNodes[nodeId].firstLink + i]; + next = ConnectedNode(m_pathNodes[nodeId].firstLink + i); if(m_pathNodes[next].bDisabled != disable && m_pathNodes[next].numLinks < 3) SwitchOffNodeAndNeighbours(next, disable); @@ -982,12 +1007,14 @@ CPathFind::SwitchRoadsOffInArea(float x1, float x2, float y1, float y2, float z1 { int i; - for(i = 0; i < m_numCarPathNodes; i++) - if (x1 <= m_pathNodes[i].pos.x && m_pathNodes[i].pos.x <= x2 && - y1 <= m_pathNodes[i].pos.y && m_pathNodes[i].pos.y <= y2 && - z1 <= m_pathNodes[i].pos.z && m_pathNodes[i].pos.z <= z2 && + for(i = 0; i < m_numCarPathNodes; i++){ + CVector pos = m_pathNodes[i].GetPosition(); + if(x1 <= pos.x && pos.x <= x2 && + y1 <= pos.y && pos.y <= y2 && + z1 <= pos.z && pos.z <= z2 && disable != m_pathNodes[i].bDisabled) SwitchOffNodeAndNeighbours(i, disable); + } } void @@ -995,12 +1022,14 @@ CPathFind::SwitchPedRoadsOffInArea(float x1, float x2, float y1, float y2, float { int i; - for(i = m_numCarPathNodes; i < m_numPathNodes; i++) - if(x1 <= m_pathNodes[i].pos.x && m_pathNodes[i].pos.x <= x2 && - y1 <= m_pathNodes[i].pos.y && m_pathNodes[i].pos.y <= y2 && - z1 <= m_pathNodes[i].pos.z && m_pathNodes[i].pos.z <= z2 && + for(i = m_numCarPathNodes; i < m_numPathNodes; i++){ + CVector pos = m_pathNodes[i].GetPosition(); + if(x1 <= pos.x && pos.x <= x2 && + y1 <= pos.y && pos.y <= y2 && + z1 <= pos.z && pos.z <= z2 && disable != m_pathNodes[i].bDisabled) SwitchOffNodeAndNeighbours(i, disable); + } } void @@ -1039,9 +1068,10 @@ CPathFind::SwitchRoadsInAngledArea(float x1, float y1, float z1, float x2, float bool disable = mode == SWITCH_OFF; for(i = firstNode; i < lastNode; i++){ - if(m_pathNodes[i].pos.z < z1 || m_pathNodes[i].pos.z > z2) + CVector pos = m_pathNodes[i].GetPosition(); + if(pos.z < z1 || pos.z > z2) continue; - CVector2D d(m_pathNodes[i].pos.x - x1, m_pathNodes[i].pos.y - y1); + CVector2D d(pos.x - x1, pos.y - y1); float dot = DotProduct2D(d, v12); if(dot < 0.0f || dot > len12) continue; @@ -1061,7 +1091,7 @@ CPathFind::MarkRoadsBetweenLevelsNodeAndNeighbours(int32 nodeId) m_pathNodes[nodeId].bBetweenLevels = true; if(m_pathNodes[nodeId].numLinks < 3) for(i = 0; i < m_pathNodes[nodeId].numLinks; i++){ - next = m_connections[m_pathNodes[nodeId].firstLink + i]; + next = ConnectedNode(m_pathNodes[nodeId].firstLink + i); if(!m_pathNodes[next].bBetweenLevels && m_pathNodes[next].numLinks < 3) MarkRoadsBetweenLevelsNodeAndNeighbours(next); @@ -1073,11 +1103,13 @@ CPathFind::MarkRoadsBetweenLevelsInArea(float x1, float x2, float y1, float y2, { int i; - for(i = 0; i < m_numPathNodes; i++) - if(x1 < m_pathNodes[i].pos.x && m_pathNodes[i].pos.x < x2 && - y1 < m_pathNodes[i].pos.y && m_pathNodes[i].pos.y < y2 && - z1 < m_pathNodes[i].pos.z && m_pathNodes[i].pos.z < z2) + for(i = 0; i < m_numPathNodes; i++){ + CVector pos = m_pathNodes[i].GetPosition(); + if(x1 < pos.x && pos.x < x2 && + y1 < pos.y && pos.y < y2 && + z1 < pos.z && pos.z < z2) MarkRoadsBetweenLevelsNodeAndNeighbours(i); + } } void @@ -1085,11 +1117,13 @@ CPathFind::PedMarkRoadsBetweenLevelsInArea(float x1, float x2, float y1, float y { int i; - for(i = m_numCarPathNodes; i < m_numPathNodes; i++) - if(x1 < m_pathNodes[i].pos.x && m_pathNodes[i].pos.x < x2 && - y1 < m_pathNodes[i].pos.y && m_pathNodes[i].pos.y < y2 && - z1 < m_pathNodes[i].pos.z && m_pathNodes[i].pos.z < z2) + for(i = m_numCarPathNodes; i < m_numPathNodes; i++){ + CVector pos = m_pathNodes[i].GetPosition(); + if(x1 < pos.x && pos.x < x2 && + y1 < pos.y && pos.y < y2 && + z1 < pos.z && pos.z < z2) MarkRoadsBetweenLevelsNodeAndNeighbours(i); + } } int32 @@ -1118,9 +1152,9 @@ CPathFind::FindNodeClosestToCoors(CVector coors, uint8 type, float distLimit, bo switch(m_pathNodes[i].unkBits){ case 1: case 2: - dist = Abs(m_pathNodes[i].pos.x - coors.x) + - Abs(m_pathNodes[i].pos.y - coors.y) + - 3.0f*Abs(m_pathNodes[i].pos.z - coors.z); + dist = Abs(m_pathNodes[i].GetX() - coors.x) + + Abs(m_pathNodes[i].GetY() - coors.y) + + 3.0f*Abs(m_pathNodes[i].GetZ() - coors.z); if(dist < closestDist){ closestDist = dist; closestNode = i; @@ -1156,10 +1190,10 @@ CPathFind::FindNodeClosestToCoorsFavourDirection(CVector coors, uint8 type, floa switch(m_pathNodes[i].unkBits){ case 1: case 2: - dX = m_pathNodes[i].pos.x - coors.x; - dY = m_pathNodes[i].pos.y - coors.y; + dX = m_pathNodes[i].GetX() - coors.x; + dY = m_pathNodes[i].GetY() - coors.y; dist = Abs(dX) + Abs(dY) + - 3.0f*Abs(m_pathNodes[i].pos.z - coors.z); + 3.0f*Abs(m_pathNodes[i].GetZ() - coors.z); if(dist < closestDist){ NormalizeXY(dX, dY); dist -= (dX*dirX + dY*dirY - 1.0f)*20.0f; @@ -1174,13 +1208,12 @@ CPathFind::FindNodeClosestToCoorsFavourDirection(CVector coors, uint8 type, floa return closestNode; } - float CPathFind::FindNodeOrientationForCarPlacement(int32 nodeId) { if(m_pathNodes[nodeId].numLinks == 0) return 0.0f; - CVector dir = m_pathNodes[m_connections[m_pathNodes[nodeId].firstLink]].pos - m_pathNodes[nodeId].pos; + CVector dir = m_pathNodes[ConnectedNode(m_pathNodes[nodeId].firstLink)].GetPosition() - m_pathNodes[nodeId].GetPosition(); dir.z = 0.0f; dir.Normalise(); return RADTODEG(dir.Heading()); @@ -1191,14 +1224,14 @@ CPathFind::FindNodeOrientationForCarPlacementFacingDestination(int32 nodeId, flo { int i; - CVector targetDir(x - m_pathNodes[nodeId].pos.x, y - m_pathNodes[nodeId].pos.y, 0.0f); + CVector targetDir(x - m_pathNodes[nodeId].GetX(), y - m_pathNodes[nodeId].GetY(), 0.0f); targetDir.Normalise(); CVector dir; if(m_pathNodes[nodeId].numLinks == 0) return 0.0f; - int bestNode = m_connections[m_pathNodes[nodeId].firstLink]; + int bestNode = ConnectedNode(m_pathNodes[nodeId].firstLink); #ifdef FIX_BUGS float bestDot = towards ? -2.0f : 2.0f; #else @@ -1206,24 +1239,24 @@ CPathFind::FindNodeOrientationForCarPlacementFacingDestination(int32 nodeId, flo #endif for(i = 0; i < m_pathNodes[nodeId].numLinks; i++){ - dir = m_pathNodes[m_connections[m_pathNodes[nodeId].firstLink + i]].pos - m_pathNodes[nodeId].pos; + dir = m_pathNodes[ConnectedNode(m_pathNodes[nodeId].firstLink + i)].GetPosition() - m_pathNodes[nodeId].GetPosition(); dir.z = 0.0f; dir.Normalise(); float angle = DotProduct2D(dir, targetDir); if(towards){ if(angle > bestDot){ bestDot = angle; - bestNode = m_connections[m_pathNodes[nodeId].firstLink + i]; + bestNode = ConnectedNode(m_pathNodes[nodeId].firstLink + i); } }else{ if(angle < bestDot){ bestDot = angle; - bestNode = m_connections[m_pathNodes[nodeId].firstLink + i]; + bestNode = ConnectedNode(m_pathNodes[nodeId].firstLink + i); } } } - dir = m_pathNodes[bestNode].pos - m_pathNodes[nodeId].pos; + dir = m_pathNodes[bestNode].GetPosition() - m_pathNodes[nodeId].GetPosition(); dir.z = 0.0f; dir.Normalise(); return RADTODEG(dir.Heading()); @@ -1243,21 +1276,21 @@ CPathFind::NewGenerateCarCreationCoors(float x, float y, float dirX, float dirY, node1 = (CGeneral::GetRandomNumber()>>3) % m_numCarPathNodes; if(m_pathNodes[node1].bDisabled && !ignoreDisabled) continue; - dist1 = Distance2D(m_pathNodes[node1].pos, x, y); + dist1 = Distance2D(m_pathNodes[node1].GetPosition(), x, y); if(dist1 < spawnDist + 60.0f){ d1 = dist1 - spawnDist; for(j = 0; j < m_pathNodes[node1].numLinks; j++){ - node2 = m_connections[m_pathNodes[node1].firstLink + j]; + node2 = ConnectedNode(m_pathNodes[node1].firstLink + j); if(m_pathNodes[node2].bDisabled && !ignoreDisabled) continue; - dist2 = Distance2D(m_pathNodes[node2].pos, x, y); + dist2 = Distance2D(m_pathNodes[node2].GetPosition(), x, y); d2 = dist2 - spawnDist; if(d1*d2 < 0.0f){ // nodes are on different sides of spawn distance float f2 = Abs(d1)/(Abs(d1) + Abs(d2)); float f1 = 1.0f - f2; *pPositionBetweenNodes = f2; - CVector pos = m_pathNodes[node1].pos*f1 + m_pathNodes[node2].pos*f2; + CVector pos = m_pathNodes[node1].GetPosition()*f1 + m_pathNodes[node2].GetPosition()*f2; CVector2D dist2d(pos.x - x, pos.y - y); dist2d.Normalise(); // done manually in the game float dot = DotProduct2D(dist2d, CVector2D(dirX, dirY)); @@ -1294,20 +1327,20 @@ CPathFind::GeneratePedCreationCoors(float x, float y, float minDist, float maxDi for(i = 0; i < 400; i++){ node1 = m_numCarPathNodes + CGeneral::GetRandomNumber() % m_numPedPathNodes; - if(DistanceSqr2D(m_pathNodes[node1].pos, x, y) < sq(maxDist+30.0f)){ + if(DistanceSqr2D(m_pathNodes[node1].GetPosition(), x, y) < sq(maxDist+30.0f)){ if(m_pathNodes[node1].numLinks == 0) continue; int link = m_pathNodes[node1].firstLink + CGeneral::GetRandomNumber() % m_pathNodes[node1].numLinks; - if(m_connectionFlags[link].bCrossesRoad) + if(ConnectionCrossesRoad(link)) continue; - node2 = m_connections[link]; + node2 = ConnectedNode(link); if(m_pathNodes[node1].bDisabled || m_pathNodes[node2].bDisabled) continue; float f2 = (CGeneral::GetRandomNumber()&0xFF)/256.0f; float f1 = 1.0f - f2; *pPositionBetweenNodes = f2; - CVector pos = m_pathNodes[node1].pos*f1 + m_pathNodes[node2].pos*f2; + CVector pos = m_pathNodes[node1].GetPosition()*f1 + m_pathNodes[node2].GetPosition()*f2; if(Distance2D(pos, x, y) < maxDist+20.0f){ pos.x += ((CGeneral::GetRandomNumber()&0xFF)-128)*0.01f; pos.y += ((CGeneral::GetRandomNumber()&0xFF)-128)*0.01f; @@ -1363,11 +1396,11 @@ CPathFind::FindRoadObjectClosestToCoors(CVector coors, uint8 type) break; // FIX: game uses ThePaths here explicitly for(k = 0; k < m_pathNodes[node1].numLinks; k++){ - node2 = m_connections[m_pathNodes[node1].firstLink + k]; - float lineDist = CCollision::DistToLine(&m_pathNodes[node1].pos, &m_pathNodes[node2].pos, &coors); + node2 = ConnectedNode(m_pathNodes[node1].firstLink + k); + float lineDist = CCollision::DistToLine(&m_pathNodes[node1].GetPosition(), &m_pathNodes[node2].GetPosition(), &coors); if(lineDist < closestDist){ closestDist = lineDist; - if((coors - m_pathNodes[node1].pos).MagnitudeSqr() < (coors - m_pathNodes[node2].pos).MagnitudeSqr()) + if((coors - m_pathNodes[node1].GetPosition()).MagnitudeSqr() < (coors - m_pathNodes[node2].GetPosition()).MagnitudeSqr()) closestMapObj = m_mapObjects[m_pathNodes[node1].objectIndex]; else closestMapObj = m_mapObjects[m_pathNodes[node2].objectIndex]; @@ -1384,7 +1417,7 @@ CPathFind::FindNextNodeWandering(uint8 type, CVector coors, CPathNode **lastNode int i; CPathNode *node; - if(lastNode == nil || (node = *lastNode) == nil || (coors - (*lastNode)->pos).MagnitudeSqr() > 7.0f){ + if(lastNode == nil || (node = *lastNode) == nil || (coors - (*lastNode)->GetPosition()).MagnitudeSqr() > 7.0f){ // need to find the node we're coming from node = nil; CTreadable *obj = FindRoadObjectClosestToCoors(coors, type); @@ -1392,7 +1425,7 @@ CPathFind::FindNextNodeWandering(uint8 type, CVector coors, CPathNode **lastNode for(i = 0; i < 12; i++){ if(obj->m_nodeIndices[type][i] < 0) break; - float dist = (coors - m_pathNodes[obj->m_nodeIndices[type][i]].pos).MagnitudeSqr(); + float dist = (coors - m_pathNodes[obj->m_nodeIndices[type][i]].GetPosition()).MagnitudeSqr(); if(dist < nodeDist){ nodeDist = dist; node = &m_pathNodes[obj->m_nodeIndices[type][i]]; @@ -1404,16 +1437,16 @@ CPathFind::FindNextNodeWandering(uint8 type, CVector coors, CPathNode **lastNode *nextNode = 0; float bestDot = -999999.0f; for(i = 0; i < node->numLinks; i++){ - int next = m_connections[node->firstLink+i]; + int next = ConnectedNode(node->firstLink+i); if(!node->bDisabled && m_pathNodes[next].bDisabled) continue; CVector pedCoors = coors; pedCoors.z += 1.0f; - CVector nodeCoors = m_pathNodes[next].pos; + CVector nodeCoors = m_pathNodes[next].GetPosition(); nodeCoors.z += 1.0f; if(!CWorld::GetIsLineOfSightClear(pedCoors, nodeCoors, true, false, false, false, false, false)) continue; - CVector2D nodeDir = m_pathNodes[next].pos - node->pos; + CVector2D nodeDir = m_pathNodes[next].GetPosition() - node->GetPosition(); nodeDir.Normalise(); float dot = DotProduct2D(nodeDir, vCurDir); if(dot >= bestDot){ @@ -1421,7 +1454,7 @@ CPathFind::FindNextNodeWandering(uint8 type, CVector coors, CPathNode **lastNode bestDot = dot; // direction is 0, 2, 4, 6 for north, east, south, west - // this could be sone simpler... + // this could be done simpler... if(nodeDir.x < 0.0f){ if(2.0f*Abs(nodeDir.y) < -nodeDir.x) *nextDir = 6; // west @@ -1456,17 +1489,14 @@ CPathFind::FindNextNodeWandering(uint8 type, CVector coors, CPathNode **lastNode static CPathNode *apNodesToBeCleared[4995]; void -CPathFind::DoPathSearch(uint8 type, CVector start, int32 startNodeId, CVector target, CPathNode **nodes, int16 *pNumNodes, int16 maxNumNodes, CVehicle *vehicle, float *pDist, float distLimit, int32 forcedTargetNode) +CPathFind::DoPathSearch(uint8 type, CVector start, int32 startNodeId, CVector target, CPathNode **nodes, int16 *pNumNodes, int16 maxNumNodes, CVehicle *vehicle, float *pDist, float distLimit, int32 targetNodeId) { int i, j; // Find target - int targetNode; - if(forcedTargetNode < 0) - targetNode = FindNodeClosestToCoors(target, type, distLimit); - else - targetNode = forcedTargetNode; - if(targetNode < 0) { + if(targetNodeId < 0) + targetNodeId = FindNodeClosestToCoors(target, type, distLimit); + if(targetNodeId < 0) { *pNumNodes = 0; if(pDist) *pDist = 100000.0f; return; @@ -1482,7 +1512,7 @@ CPathFind::DoPathSearch(uint8 type, CVector start, int32 startNodeId, CVector ta for(i = 0; i < 12; i++){ if(startObj->m_nodeIndices[type][i] < 0) break; - if(m_pathNodes[startObj->m_nodeIndices[type][i]].group == m_pathNodes[targetNode].group) + if(m_pathNodes[startObj->m_nodeIndices[type][i]].group == m_pathNodes[targetNodeId].group) numPathsToTry++; } }else{ @@ -1498,39 +1528,39 @@ CPathFind::DoPathSearch(uint8 type, CVector start, int32 startNodeId, CVector ta if(startNodeId < 0){ // why only check node 0? if(m_pathNodes[startObj->m_nodeIndices[type][0]].group != - m_pathNodes[targetNode].group) { + m_pathNodes[targetNodeId].group) { *pNumNodes = 0; if(pDist) *pDist = 100000.0f; return; } }else{ - if(m_pathNodes[startNodeId].group != m_pathNodes[targetNode].group) { + if(m_pathNodes[startNodeId].group != m_pathNodes[targetNodeId].group) { *pNumNodes = 0; if(pDist) *pDist = 100000.0f; return; } } - for(i = 0; i < 512; i++) - m_searchNodes[i].next = nil; - AddNodeToList(&m_pathNodes[targetNode], 0); + for(i = 0; i < ARRAY_SIZE(m_searchNodes); i++) + m_searchNodes[i].SetNext(nil); + AddNodeToList(&m_pathNodes[targetNodeId], 0); int numNodesToBeCleared = 0; - apNodesToBeCleared[numNodesToBeCleared++] = &m_pathNodes[targetNode]; + apNodesToBeCleared[numNodesToBeCleared++] = &m_pathNodes[targetNodeId]; // Dijkstra's algorithm // Find distances int numPathsFound = 0; - if(startNodeId < 0 && m_mapObjects[m_pathNodes[targetNode].objectIndex] == startObj) + if(startNodeId < 0 && m_mapObjects[m_pathNodes[targetNodeId].objectIndex] == startObj) numPathsFound++; for(i = 0; numPathsFound < numPathsToTry; i = (i+1) & 0x1FF){ CPathNode *node; - for(node = m_searchNodes[i].next; node; node = node->next){ + for(node = m_searchNodes[i].GetNext(); node; node = node->GetNext()){ if(m_mapObjects[node->objectIndex] == startObj && (startNodeId < 0 || node == &m_pathNodes[startNodeId])) numPathsFound++; for(j = 0; j < node->numLinks; j++){ - int next = m_connections[node->firstLink + j]; + int next = ConnectedNode(node->firstLink + j); int dist = node->distance + m_distances[node->firstLink + j]; if(dist < m_pathNodes[next].distance){ if(m_pathNodes[next].distance != MAX_DIST) @@ -1553,7 +1583,7 @@ CPathFind::DoPathSearch(uint8 type, CVector start, int32 startNodeId, CVector ta for(i = 0; i < 12; i++){ if(startObj->m_nodeIndices[type][i] < 0) break; - int dist = (m_pathNodes[startObj->m_nodeIndices[type][i]].pos - start).Magnitude(); + int dist = (m_pathNodes[startObj->m_nodeIndices[type][i]].GetPosition() - start).Magnitude(); if(m_pathNodes[startObj->m_nodeIndices[type][i]].distance + dist < minDist){ minDist = m_pathNodes[startObj->m_nodeIndices[type][i]].distance + dist; curNode = &m_pathNodes[startObj->m_nodeIndices[type][i]]; @@ -1567,7 +1597,8 @@ CPathFind::DoPathSearch(uint8 type, CVector start, int32 startNodeId, CVector ta } if(pDist) *pDist = minDist; - }else{ + }else + { curNode = &m_pathNodes[startNodeId]; *pNumNodes = 0; if(pDist) @@ -1575,9 +1606,9 @@ CPathFind::DoPathSearch(uint8 type, CVector start, int32 startNodeId, CVector ta } // Trace back to target and update list of nodes - while(*pNumNodes < maxNumNodes && curNode != &m_pathNodes[targetNode]) + while(*pNumNodes < maxNumNodes && curNode != &m_pathNodes[targetNodeId]) for(i = 0; i < curNode->numLinks; i++){ - int next = m_connections[curNode->firstLink + i]; + int next = ConnectedNode(curNode->firstLink + i); if(curNode->distance - m_distances[curNode->firstLink + i] == m_pathNodes[next].distance){ curNode = &m_pathNodes[next]; nodes[(*pNumNodes)++] = curNode; @@ -1598,6 +1629,7 @@ bool CPathFind::TestCoorsCloseness(CVector target, uint8 type, CVector start) { float dist; + if(type == PATH_CAR) DoPathSearch(type, start, -1, target, pNodeList, &DummyResult, 32, nil, &dist, 999999.88f, -1); else @@ -1661,10 +1693,10 @@ CPathFind::DisplayPathData(void) // Render car path nodes if(gbShowCarPaths) for(i = 0; i < m_numCarPathNodes; i++){ - if((m_pathNodes[i].pos - pos).MagnitudeSqr() > SQR(maxDist)) + if((m_pathNodes[i].GetPosition() - pos).MagnitudeSqr() > SQR(maxDist)) continue; - CVector n1 = m_pathNodes[i].pos; + CVector n1 = m_pathNodes[i].GetPosition(); n1.z += 0.3f; // Draw node itself @@ -1673,8 +1705,8 @@ CPathFind::DisplayPathData(void) 0xFFFFFFFF, 0xFFFFFFFF); for(j = 0; j < m_pathNodes[i].numLinks; j++){ - k = m_connections[m_pathNodes[i].firstLink + j]; - CVector n2 = m_pathNodes[k].pos; + k = ConnectedNode(m_pathNodes[i].firstLink + j); + CVector n2 = m_pathNodes[k].GetPosition(); n2.z += 0.3f; // Draw links to neighbours CLines::RenderLineWithClipping(n1.x, n1.y, n1.z, @@ -1686,12 +1718,12 @@ CPathFind::DisplayPathData(void) // Render car path nodes if(gbShowCarPathsLinks) for(i = 0; i < m_numCarPathLinks; i++){ - CVector2D n1_2d = m_carPathLinks[i].pos; + CVector2D n1_2d = m_carPathLinks[i].GetPosition(); if((n1_2d - pos).MagnitudeSqr() > SQR(maxDist)) continue; int ni = m_carPathLinks[i].pathNodeIndex; - CVector pn1 = m_pathNodes[ni].pos; + CVector pn1 = m_pathNodes[ni].GetPosition(); pn1.z += 0.3f; CVector n1(n1_2d.x, n1_2d.y, pn1.z); n1.z += 0.3f; @@ -1701,7 +1733,7 @@ CPathFind::DisplayPathData(void) n1.x, n1.y, n1.z + 1.0f, 0xFFFFFFFF, 0xFFFFFFFF); CLines::RenderLineWithClipping(n1.x, n1.y, n1.z + 0.5f, - n1.x+m_carPathLinks[i].dir.x, n1.y+m_carPathLinks[i].dir.y, n1.z + 0.5f, + n1.x+m_carPathLinks[i].GetDirX(), n1.y+m_carPathLinks[i].GetDirY(), n1.z + 0.5f, 0xFFFFFFFF, 0xFFFFFFFF); // Draw connection to car path node @@ -1723,9 +1755,9 @@ CPathFind::DisplayPathData(void) for(j = 0; j < m_pathNodes[ni].numLinks; j++){ k = m_carPathConnections[m_pathNodes[ni].firstLink + j]; - CVector2D n2_2d = m_carPathLinks[k].pos; + CVector2D n2_2d = m_carPathLinks[k].GetPosition(); int nk = m_carPathLinks[k].pathNodeIndex; - CVector pn2 = m_pathNodes[nk].pos; + CVector pn2 = m_pathNodes[nk].GetPosition(); pn2.z += 0.3f; CVector n2(n2_2d.x, n2_2d.y, pn2.z); n2.z += 0.3f; @@ -1740,10 +1772,10 @@ CPathFind::DisplayPathData(void) // Render ped path nodes if(gbShowPedPaths) for(i = m_numCarPathNodes; i < m_numPathNodes; i++){ - if((m_pathNodes[i].pos - pos).MagnitudeSqr() > SQR(maxDist)) + if((m_pathNodes[i].GetPosition() - pos).MagnitudeSqr() > SQR(maxDist)) continue; - CVector n1 = m_pathNodes[i].pos; + CVector n1 = m_pathNodes[i].GetPosition(); n1.z += 0.3f; // Draw node itself @@ -1752,8 +1784,8 @@ CPathFind::DisplayPathData(void) 0xFFFFFFFF, 0xFFFFFFFF); for(j = 0; j < m_pathNodes[i].numLinks; j++){ - k = m_connections[m_pathNodes[i].firstLink + j]; - CVector n2 = m_pathNodes[k].pos; + k = ConnectedNode(m_pathNodes[i].firstLink + j); + CVector n2 = m_pathNodes[k].GetPosition(); n2.z += 0.3f; // Draw links to neighbours CLines::RenderLineWithClipping(n1.x, n1.y, n1.z, @@ -1763,9 +1795,9 @@ CPathFind::DisplayPathData(void) // Draw connection flags CVector mid = (n1+n2)/2.0f; uint32 col = 0xFF; - if(m_connectionFlags[m_pathNodes[i].firstLink + j].bCrossesRoad) + if(ConnectionCrossesRoad(m_pathNodes[i].firstLink + j)) col += 0x00FF0000; - if(m_connectionFlags[m_pathNodes[i].firstLink + j].bTrafficLight) + if(ConnectionHasTrafficLight(m_pathNodes[i].firstLink + j)) col += 0xFF000000; CLines::RenderLineWithClipping(mid.x, mid.y, mid.z, mid.x, mid.y, mid.z + 1.0f, |