서버가 게임 클라이언트에게 주변에 보이는 다른 플레이어를 효율적으로 알리는 방법?

Question

저는 멀티 플레이어 플래시 게임을하고 있습니다. 서버는 각 클라이언트에게 다른 플레이어가 플레이어 근처에 무엇이 있는지 알려줍니다. 이를 위해 서버는 어떤 클라이언트가 서로 가까이 있는지 확인해야합니다. 다음은 임시 솔루션으로 현재이 순간에 사용하고있는 내용입니다.

private function checkVisibilities() 
{ 
    foreach ($this->socketClients as $socketClient1) 
    { //loop every socket client 
     if (($socketClient1->loggedIn()) && ($socketClient1->inWorld())) 
     { //if this client is logged in and in the world 
      foreach ($this->socketClients as $cid2 => $socketClient2) 
      { //loop every client for this client to see if they are near 
       if ($socketClient1 != $socketClient2) 
       { //if it is not the same client 
        if (($socketClient2->loggedIn()) && ($socketClient2->inWorld()) 
        { //if this client is also logged in and also in the world 
         if ((abs($socketClient1->getCharX() - $socketClient2->getCharX()) + abs($socketClient1->getCharY() - $socketClient2->getCharY())) < Settings::$visibilities_range) 
         { //the clients are near each other 
          if (!$socketClient1->isVisible($cid2)) 
      { //not yet visible -> add 
           $socketClient1->addVisible($cid2); 
          } 
         } 
         else 
         { //the clients are not near each other 
          if ($socketClient1->isVisible($cid2)) 
          { //still visible -> remove 
           $socketClient1->removeVisible($cid2); 
          } 
         } 
        } 
        else 
        { //the client is not logged in 
         if ($socketClient1->isVisible($cid2)) 
         { //still visible -> remove 
          $socketClient1->removeVisible($cid2); 
         } 
        }  
       } 
     } 
    } 
} 

잘 작동합니다. 그러나 지금까지 한 번에 2 명의 플레이어 만 플레이했습니다. 이 함수는 모든 클라이언트에 대해 모든 클라이언트를 루핑합니다. 그래서 100 명의 플레이어가 100 * 100 = 10.000 루프가 될 때마다 기능이 실행됩니다. 이것은 최선 또는 가장 효율적인 방법으로 보이지 않습니다.

이제는 여러분이 내 현재 설정에 대해 어떻게 생각하는지, 그리고 이러한 가시성을 다루는 더 좋은 방법에 대한 제안이 있다면 궁금합니다.

업데이트 : 전 세계가 무한하다는 것을 잊었습니다. 그것은 실제로 "우주"입니다. 지도가 없습니다. 또한 2 차원 게임입니다.

미리 감사드립니다.

_|____|____|____|_ 
| | | | 
_|____|____|____|_ 
| | | | 
_|____|____|____|_ 
| | | | 
_|____|____|____|_ 
| | | | 

을 그리고 서로 교차 어떤 격자 타일로 당신의 개체 삽입 :

이제

_|____|____|____|_ 
| @ | | | 
_|____|____|____|_ 
| |d d | | 
_|____|____|____|_ 
| | d | d | 
_|____|____|____|_ 
| | | | 

이 할을

Answer 1

가장 간단한 솔루션과 같이, 균일 한 그리드로 세계를 분할하는 것입니다 근처의 물체를 쿼리하면 근처의 셀만 살펴 봐야합니다. 예를 들어, 플레이어 (@)에서 하나 개의 타일 내에서, 당신은 단지 9 개 타일 확인하지 전체지도를 필요로하는 참조 :

 
/|////|////|____|_ 
/|/@//|////| | 
/|////|////|____|_ 
/|////|d/d/| | 
/|////|////|____|_ 
| | d | d | 
_|____|____|____|_ 
| | | | 

당신의 세계에 따라, 그러나,이 기술은 매우 낭비 될 수 있습니다 빈 셀이 많이있을 수 있습니다. 문제가되는 경우 spatial index을 구현하는 것이 좋습니다.

Answer 2

플레이어의 위치를 ​​나타내는 쿼드 트리를 사용해보십시오.
위키 문서는 here입니다.
필요한 것은 공간 (평면)을 필요한만큼 분할하는 트리에서 공간 (사용자)에있는 객체를 유지하는 것입니다. 무한 문제에 관해서는 프로그래밍에서 아무 것도 실제로 무한하지 않으므로 사용자가 전달할 수없는 경계를 정의하십시오. 좌표가 너무 큰 경우에도 100 년 정도 소요되는 좌표로 이동하십시오.).

Answer 3

내가 말할 수있는 첫 번째 사항은 코드가 바깥쪽으로 보이는 것입니다. 왜 어떤 클라이언트가 로그인했는지, 세계 어느 곳에 있는지 확인하는 일을해야만하는 높은 수준의 게임 로직 기능을 가지고 있습니까? 모든 네트워킹 아이템은 게임 로직에서 제거되어야 더 높은 레벨에서 수행되고 게임 내 로직은 현재 플레이하고있는 플레이어와 세계에서 처리해야합니다. 이것은 간단한 질문으로 당신을 남겨 둡니다.이 두 선수는 서로 충분히 가깝습니까? 이미 가지고있는 것처럼 간단한 거리 확인만으로도 충분합니다.

다음으로하는 일은 루핑 양을 줄이는 것입니다. 거리는 일반적으로 교환 속성이므로 B와 A 사이뿐만 아니라 A와 B 사이의 거리를 확인할 필요가 없습니다. 이렇게하려면 첫 번째 루프가 모든 클라이언트를 거치지 만 두 번째 루프는 반복해야합니다 첫 번째 이후에 오는 모든 고객. 이렇게하면 필요한 반복 횟수가 반으로 줄어 듭니다.

상태에 따라이 작업을 계속 수행 할 필요가 없습니다. 게임이 원활하게 실행될 수 있도록 자주 수행해야합니다. 이동 속도가 그다지 높지 않으면 몇 초마다이 작업을 수행하면 충분합니다.

여전히 충분하지 않은 경우 ianh에서 설명한대로 일종의 공간 해싱 시스템을 사용하면 수행하는 쿼리의 수를 줄일 수 있습니다. 그리드가 가장 쉽지만 일종의 트리 구조 (이상적으로는 자체 균형 조정)가 또 다른 옵션입니다.