????MMORPG??????????

D??

?/??

??????2018???????????????????????????????????????online???????????????????????????????????????????

?????CPU????

1.1????JPS??

MMORPG??????????NPC?????A*?????????????????????????????

???????JPS??????????????????????????????????????????????????200????????104???????A*??????2.6074x1011??????109???????JPS?????1.7037x1010???????????JPS????JPS-Bit??????3.2364x109??????????????JPS????JPS-BitPrune??????2.3703x109?????????????JPS????JPS-BitPre??????2.0043x109????????????????????JPS????JPS-BitPrunePre??????9.5434x108???

?????????200???????JPS???????????????1.7???0.32???0.23???0.02???0.095??????????A*???15??81??110??130??273???????A*????????????????????

?????2012?2014??????????????????Grid???????GPPC?The Grid-Based Path Planning Competition???JPS????????????????????????????????

1.1.1 JPS????

JPS?????????Jump Point Search?????????????2011??????Grid????????A*????????1.1.1.1.1???JPS?????A*???????????????A*????????????????JPS?A*???????????????1.1.1.1.1???A*?JPS???????????1.1.1.1.1???JPS?A*????????????????????A*????????????????????????????????JPS??????current??????????????????????�?????????�???1.1.1.1.2?????????????????????????????????????

???current??????????

?1???current????????????????????????current??????????closedset????

?2???current?????????current????????closed??????

?3???current???????????????????????current??????????closedset????

???current???????????

?1???current??????????????current???????????????????current?????????????closedset????

?2???current?????????current????????closedset????

?3???current??????????????current???????????????????current?????????????closedset????

JPS??????????????????????????????????

?1.1.1.1.1 A*?JPS????????

?1.1.1.1.1 A*????

?1.1.1.1.2 JPS???�?????????�

1.1.1.2 JPS????

?1.1.1.2.1 ?????????5*5????

??????JPS??????????????1.1.1.2.1???5*5????????????S????E????JPS????S?E????????????S??openset??openset??F?????S???openset?????closedset?S????????????????????????????????????????????????????????????????????????????G????????????3???parent(G)?S?praent(G)?S?????????G????????????????????I???G??? ??G??openset??openset??F?????G???openset?????closedset???G????????????S?G?????????????????????????????????????????????????????2??????I??I??openset??openset??F?????I???openset?????closedset???I????????????G?I??????I??I????????????????????????????????????????????????Q???????????2????????Q??openset??openset??F?????Q???openset?????closedset???Q???????????Q????????????????????????????????????????????????E???????????1????????E??openset??openset??F?????E???E???????????????S?G?I?Q?E?

?????????H???K?????????????????????????????????H?K?????????H???????????JPS???????????H?K???????????????????????H?K???????S?G?H?K?M?P?E?????????????

???JPS?????????A*?????????S?A??????????A?????A*?????F?G?B?H???openset????JPS??????????openset??F?G?H????????S?A?F??????S?F?????S?F???????S?A?F?????S?A?G??????????????????1?????A?????F?G???F?G????openset???S?A?H?S?H???????????S?G?H?????????A??????????1????S??A???????????H???H?????openset??B????????????B??????????openset?????C???

?1.1.1.2.1???A*?JPS??????????D. Age: Origins?D. Age 2?StarCraft??????????????????2????????????M.Time????openset?closedset????G.Time??????????????A*???58%??????openset?closedset?42%???????????JPS??14%?????openset?closedset?86%?????????????openset????????????????????JPS?A*???????????????????log(n)???????????????????log(n)????????S?E?????????openset???S?G?I?Q?E?

?1.1.1.2.1 A*?JPS???????

1.1.2 JPS??????

1.1.2.1 JPS????JPS-Bit??????

????????JPS-Bit?????????????????JPS?????????????1.1.2.1.1?????????????????JPS?????????????????????I????????????????????1??????0??????I???B????????bit?00000100???I???B-????????bit?00000000???I????B+????????bit?00110000?????????????????CPU???__builtin_clz(B)?????0????????????5?????0???????????????__builtin_clz(((B->>1) && !B-) ||((B+>>1) && !B+)) ????????(B+>>1) && !B+??(00110000 >> 1) && 11001111??00001000??(B->>1) &&!B?00000000???__builtin_clz(((B->>1) && !B-) ||((B+>>1) && !B+))?__builtin_clz(00001000)?4???????4???M??0???????????_builtin_ffs(((B-<<1) && !B-) ||((B+<<1) && !B+))?__builtin_ffs(x)??x?????1???????????7368?1110011001000???4?????????bit????????????????bit?????????

??JPS-Bit?????????????CPU?????????JPS?????????????JPS-Bit??????????JPS????JPS-Bit??????JPS??5????

?1.1.2.1.1?????????3*8????

1.1.2.2 JPS????JPS-BitPrune?????????

???????????JPS-BitPrune?JPS-Bit???????????????????????????1.1.1.1.2?????(3)?????????????????????????????�??�??????????????????openset???????????JPS-BitPrune?????????????????????????????????????????????????????????

????????????JPS-BitPrune????????????JPS-BitPrune?????????????????????????????????????????????????????????????????????JPS-BitPrune??????????

???????????start(jp1)?jp2?jp3...jpk..end(jpn)??????????jpi?jpi+1?????jpi?jpi+1?x????y????????????????????????????????????????????????????jpi?jpi+1?x???y????????1???x????dx??jpi?x????jpi+1?x????y????dy?????????????????????????????????????????????2???x????dx?y????dy????????????????????????????????????????????????jpi?jpi+1??????????jpi???jpi+1????????????jpi?jpi+1????????????????jpi?jpi+1?????????????????????jpi+1?????????????????????jpi???????min(dx,dy)???????

?1.1.2.2.1 JPS-BitPrune???????

????1.1.2.2.1 ???????JPS-BitPrune????????????????S????(1,1)??S(1,1)????1?4?6???????????2?3???????(2)?????????1???????2?3??????????4?6????????????????????????????????????????????????1.1.2.2.1 ????1????????2?3?4?????4?????????????????1????2?3???????1????S???????????4????4?????5???????4????S???4???????1????1?????????????S????????????6????6?????7???????6????S???6???????4????4?????4??????1???????????S??

?????????????????????????S???????????????1????????????????????2?3????2?3????????S??????????????????4???????????????????5????5????????S??????????????????6?????????????????7????7????????S???JPS-BitPrune????S(1,1) ???7(4,6)?

?????S(1,1)?????????????????7(4,6)???????????????????????dx?3?dy?5????S?????3?????6(4,4)?????????????1.1.2.2.1 ?????JPS-BitPrune??????????S(1,1) ???6(4,4) ???7(4,6)?

1.1.2.2.1 ???????

???????????JPS????????????????????

???????? ??????????????????S?????7????????

???S???????????1?openset??????1?

?openset??F???????1??????1?????????????????????2?3????????????4???openset???2?3?4?

?openset??F???????4??????4???????????????????5??????????6???openset???2?3?5?6?

?openset??F???????6?????????7???openset???2?3?5?7?

?openset??F????????7????????????????????S(1,1)???1(2,2) ???4(3,3) ???6(4,4) ???7(4,6)?JPS???????7?????????????1?4?6?

??????????? ?????????????S?????7???????????

???S???????????????1????????????????????2?3????2?3????????S??????????????????4???????????????????5????5????????S??????????????????6?????????????????7????7????????S??????????????????????????openset???2?3?5?7?

?openset??F????????7???????????????????S(1,1) ???7(4,6)????????JPS????????1?4?6??JPS-BitPrune????1?4?6???????????????????????????????????

1.1.2.3 JPS????JPS-BitPre????????

????????????????JPS+?JPS-BitPre?JPS-BitPrunePre??????????????????????????????????????????????????????????????JPS-BitPre????JPS-Bit????????????????????????????????step???step????JPS???????????�??�????????????????JPS???????????????????????N*N?????????????16????????????N*N*8*16bit???N?1024???????????16M???????????????JPS?????????????????????????1024*1024????????1?????????2048*2048????????????????

???step??????????????????????step???????????step????????????

????1.1.2.3.1??N??????????8??2??
????????4??4??
????????6??3??
????????2???2????????2????????5??
????????7??2??
????????1????1????????3??????????1??
????????5??3??
????????3???3????????3??????????3??

?1.1.2.3.1  JPS-BitPre???????

??1.1.2.3.1?????????????N???T????JPS-BitPre????????

?openset????N? ?N??????????????????????????step????????????????????{1?2?3?4?5?6?7?8}???1.1.2.3.1????????1?2?3???????????????openset?????4?5?6?7?8???????T???N??????????????????????T???????????5???????????4?6?7?8???????N?5?????N??3???N?T?x??????dx?1?y??????dy?2???????N???5????min(dx,dy)????11???openset?

?openset??F?????11?????????T???openset????openset??F?????T???????????????????N(4,5)???11(3,4) ???T(3,3)?

????JPS-BitPre?????????????????JPS-Bit?N?T??????????

?openset????N????????????????1?3?11????????3??????????openset???2?????????2??????????openset?

?openset??F?????11?????????T???openset?

?openset??F?????T????????????????????N(4,5)???11(3,4) ???T(3,3)?

???????????JPS-BitPre????????JPS-Bit?????????????????JPS-BitPre?????????????????????????????????step?????openset?????????????????

1.1.2.4 JPS??????????????

??1.1.2.4.1?????S??????E?????????????????S?E?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

????Grid????????????1.1.2.4.1????????????????????????????????????????1.1.2.4.1?????1.1.2.4.1??S?1?2?????????1??3?4?E?????????2?S?E???????????S?E??????????????????1.1.2.4.1??????????????????????O(N)?N?Grid???????????????????????????????O(1)?

?1.1.2.4.1 ??????S?E

?1.1.2.4.1 ??????

1.1.2.5 JPS??????????

openset????????????????????????????????????????O(logn)???????????????????????????????????????????????G??F???????????????openset????????????????O(n)????????closedset??????openset?????????????????????????????????????closedset?????????

?????????1km*1km??????2k*2k?????matrix???????pnode??????????????????id??????expanded(????closedset?)?G??F???????parent?????????index?12?byte?????(x,y)??????????????????matrix???(x,y)???pnode??????????????????????????new??????????????openset??????shift up?shift down???????????????index???????????????????????expand????????????closedset???????????????openset????matrix(x,y)????openset????index??????????matrix(x,y)?openset(index)??????????????????????????G??F????????????????????openset?closedset???????O(1)?????????????????????matrix??????????????matrix???

1.1.3 ?????

??????????????????????????JPS??????????????????????????????JPS?????????????????thread_local????????????openset?closedset?????????????????matrix???????????????????????????matrix????????????A???????????expanded?????B?????????????????????????????????

1.1.4 JPS??????

1.1.4.1 ??

JPS???????????0.5m*0.5m??????1bit??1km*1km???????2k*2k/8?byte??0.5M?????????????32??????????32????????????????90????????

??JPS????????????????????????????????15??????2k*2k/2?byte??2m?????????????0.5m?????????0.5m??????2m??3m??????????????????????openset?closedset????????????????matrix?1km*1km?????????0.5m*0.5m?????matrix???????2k*2k*4byte??8m??????????matrix?????thread_local???????16???????16*8m??128m????????????????????

???2k*2k??100*100????20*20???20*20????????firLayerMatrix?100*100??????secLayerMatrix?firLayerMatrix?400????400???????????????????????firLayerMatrix?(x,y)?????????new?100*100*4byte?secLayerMatrix?secLayerMatrix???????????????????new??????

?????2k*2k??????(231,671)?????????????firLayerMatrix?(2,6)???????????????new?100*100*4byte?secLayerMatrix????secLayerMatrix??(31,71)????????????????????????new???????openset????????expanded?????????????closedset??????????????openset????????G??F????????????NPC??????????JPS???????80*80???secLayerMatrix?100*100????????secLayerMatrix????matrix????20*20*4byte+100*100*4byte??0.04m?

??16?????????????????0.5m?????????0.5m??????2m???matrix0.04m*16??3.64M??????????20??????JPS????72.8M?

1.1.4.2 ???

?JPS???????????????openset????new?????????????????id???????????12?byte??????????????new??????????????????new?????????????????????????????????????????????????????

???????????

??????????????800?????new???????800??????????????JPS??NPC????NPC????????????NPC???????20m?????????40m*40m????80*80?6400????????????????????1/10? ???????640???800????????800???????800byte*12???9.6k??????

??secLayerMatrix???100*100*4byte??????????????????secLayerMatrix?????????????????????????????secLayerMatrix???100*100*4byte?????????????????????????????????secLayerMatrix??????0.04m?

1.1.5 ????

??1.1.4.1??????????????????????????????JPS????????????????????????????????????????JPS?????????????????????????????????JPS???????????????????

??JPS???????A?B?C?D?E?F?G?H??????A????????A?C?????????A?C????????A?D?????????A?D?????????A?E???A?E????????????A?D?E?F?G?H???D?????D?F?????????D?F?????????D?G???D?G????????????A?D?F?G?H??????????H????????????????JPS?????1/5??????????????????????????????????????????????????????????????

?1.1.4.1

1.2?????????

1.2.1 ?????????

1.2.1.1 ???

?????????????????NPC?????????Non-Player-Controlled Character??WRAP?????????????????????????????????????????????????????????????????????????????????????????????????????????????????1????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

????Me???5??????????????????????????????????????Me????????He????????????????Me?He??????????Me??????????????????????Me???5?????8?????????????????????????????

?1.2.1.1.1 ?????????5?????8

1.2.1.2 ????????

?????????MMO?Massively Multiplayer Online??????????????????????????????????????????????????????????????????????????????????????????

MMO????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

??????????100????????????????????????????????????????????99?????????????100*99???????????????????????????????????????????????????????????????

????????????????????????????????????????????????????O(1)?

1.2.2 ?????

?????????????1.2.1.1???ViewLinkNodePair????ViewLinkNode?????ViewLinkNode????1.2.1.2?????ViewLinkNodePair?????m_Parents???Obj_User?????m_pUser?m_pUser??????????ViewLinkNodePair??ViewLinkNode????????m_pUser??????m_pUser???????????????????????????????????????

?1.2.1.1

?1.2.1.2

1.2.3 ????

????????????????????????????ViewLinkNodePair????ViewLinkNode???ViewLinkNode???ViewLinkNodePair??????????A?B????????ViewLinkNodePair?A?ViewLinkNodeA??ViewLinkNodePair?B?B?ViewLinkNodeB??ViewLinkNodePair?A????A?B????????A??????????B?ViewLinkNodeA????A?????????????B?ViewLinkNodeA???ViewLinkNodePair??ViewLinkNodePair?????A?ViewLinkNodeB??B?????????

?????????CChainItem<ViewLinkNode>???????CChainItem????1.2.2.1???data???ViewLinkNode??????1.2.2.2????????rObjA?rObjB??????????????g_ViewLinkPool?????????????pPair??pPair?m_LinkNodeA?m_pUser??rObjB????m_LinkNodeB?m_pUser??rObjA????m_Parents??pPair??????rObjA?rObjB???????????rObjA???????????CChainItem<ViewLinkNode>????????m_LinkNodeA??m_pUser??rObjB?????????????????rObjA?????????????m_LinkNodeA?m_Parents?????pPair???pPair???m_LinkNodeB?m_LinkNodeB?m_pUser??rObjA?????m_LinkNodeB?rObjB?????????

?1.2.2.1

?1.2.2.2

1.2.4 ???

??????????????????????????????+?????????????????????????????????O(n)???????????????????????????????Obj????????????????Obj?????2048?ObjID???0?2047????????????bit????????????2047?bit???????2047?Obj????0.25K?3000????????????0.75M???He?ObjID?10???Me????He??????Me??10???????1???

1.2.5 ??????

??1.2.1.1.1?????Me???5?????8???????????????????????????????????????????????Me?????????????????????1?????????????????????He????1?????He????2?????He????????????????He????1??????He???????????EnterList?????Me??????????He?????1?????He???????????????LeaveList???????He???Me?????????

??Me???5????????????User1?User2?User3?User4?User5?User6?Me?????8??????????????User3?User4?User5?User6?User7?User8????????User1?User6???????1????User3?User8??????User3?User6????1?????4??????2??User7?User8????1??????????EnterList????????User1?User2???????1???????????LeaveList???????????pPair?

?LeaveList?????User1?User2?????pPair?????Me?User1?User2??????????CChainItem<ViewLinkNode>???????????

?EnterList?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????EnterList?????User7?User8???ViewLinkNodePair???ViewLinkNode????????????

1.3 ?????????

1.3.1 ????

?????????????????????????????????????????????

MMORPG????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????500ms??????????????????????????????????????????????????????10%?

?????n????k?????????????????n?????????????????????????????n????????????????????????????????????????????????????k????????????????n??????????????

??????????set????????set????????O(logn)???m????set???????????O(log(1*2*..*m))???????????????????m??????????p???set????????O(log(1*2..*m*p)????????m????????????m?????????????????????set?o2?????1.3.1.1????50??????165639?????1.3.1.2????50??????1522???set???108??????????????????????????????????????????????????50??????????

????????????????????????????????k???????????????????????????????????k????????????????????????

?1.3.1.1

?1.3.1.2

1.3.2 ????

???????????????????????????????????????1???????1.3.2.1????????n?10001100??????7??????????????????????????????????????????????????????1????????n - 1?10001011?n & (n - 1)?10001000??????3?????0?????????????????????n????1????? n = n & (n-1)?????n??????????1?????1.3.2.2???

?1.3.2.1

?1.3.2.2

??????gcc??????__builtin_ffs(uint32 n)???n?????1???????????????n?10001100??__builtin_ffs(n)?3???????x86?????O0??????1.3.2.3?????????????????64?????__builtin_ffsll(uint64 n)?

?1.3.2.3

??????????????????64?????64????bit??????????64bit??64bit??uint64?n????__builtin_ffsll??????1???????????????????n&(n-1)??????1??n?0????????64????2?????9????????64bit???0...0100000010????__builtin_ffsll????2?????????n=n&(n-1)??0...0100000000???__builtin_ffsll????9?????????n=n&(n-1)??0??????????64??????????????????????

??????????switch?????if????????????????if????????????????switch???case??????gcc?O0???case????5??????????????????O(1)????????case???switch?????case??????????????case???????gcc?O0???case??5?????????????????????????????????64???????????????120????64?????????63????32??16??8???????????????????????

1.3.3 ????

num???uint64?????????num??2????64?????num?100...010??1.3.3.1????????????????????num & 1??0?????j????????1.3.3.2?????????????index????????????????1.3.3.1??2011????1.3.3.2??26???????77?????????????????????????????????????????????????

?1.3.3.1

?1.3.3.2

1.4 ???????????

????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

??????????????????????K???????????????????????????????????O(n)??????????????????????1?5??????????????????????????????????????????????????????????K????????????????????????????????????????????????????????K?????????????????????????????????????????????????????????????????????????????????

?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...?????????????????set???????????????????????????????????????????...??????????????????????????????????set???????set???????????????????????????????????????????????????????????????????

???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????map??map?key?????key??????????????????????????????????...??????????????map?value???vector???vector?????key???????????????????????????????map????????????????????????????????????????????????

1.5 ??????

????????????????????????Encode???????memcpy??????memcpy??????O(n)??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

?????????c++?queue???????????????????queue????????????????????????????????????????????????????????????????Byte?????K???????????????????????Byte??????????K????

??????Tconnd?????????Tconnd??????TFRAMEHEAD????????12K???TFRAMEHEAD_CMD_START??????TFRAMEHEAD??Tconnd?????????????????????TFRAMEHEAD????????????????????? ????TFRAMEHEAD_CMD_START?????TFRAMEHEAD?????????????12K???????????????TFRAMEHEAD????????????????????????????????TFRAMEHEAD??????????????????????

1.6 ??Cache

?????????????????????????????????GameServer1??????????????GameServer2??????????????????????????????????????GameServer1 -> WorldServer -> GameServer2 -> WorldServer -> GameServer1???????????????????????????????????????????????????????

???????????????????cache????????????????1????????????????????GameServer1??A??GameServer1???B????????????????B???2????????????????????????????GameServer1??A??GameServer2???C??GameServer1???cache?????C?????C????????10?????????C???????C??????????????3?????????????cache????????????GameServer????cache???????

?????????????????????????????????????????????????????????????????????80%-90%???

?????????

2.1 ????

????????????????????????????????perf?gprof?????????????????????????????linux?/proc/self/statm????????????????????vsize???????resident???????share ???????text ????????lib ????????data_stack ??/????????dt ????????????????????????getpagesize()???byte???????????vsize??????????????????

???????????????????????????????????????????????CLion??visual studio????????????????????gdb?????

p ((unsigned long)(&((ClassName*)0)->MemberName))???????ClassName?????MemberName?????????????????????????????????????????????????????????????????????

2.2 ????

???????????????????????????????????????????????valgrind?????????????valgrind?????CPU?????????????????????????????????????valgrind?????????????????glibc????????????????????????????2.2.2?2.2.3????????????????????????????????????????????????????????????????????????????????????????????????

?????????vec_stack???????????????????vec_stack??????vec_stack????????????vec_stack??????????vector???????????????map?map?????????????????????????2.2.1???my_back_hook?????malloc?free?????2.2.2???my_init_hook?malloc?free???????????

???????????????????my_malloc_hook????2.2.2????my_malloc_hook?????my_recover_hook?malloc???????????????????????malloc?????size????????????????????????????stTrace.m_pAttr??????????m_nSize?????m_szCallTrace????????vec_stack???????m_nSize?????????????????vec_stack?????????????????????????vec_stack??my_malloc_hook?????malloc???????malloc?

???????????????????my_malloc_free????2.2.3????my_malloc_free?????my_recover_hook?free??????????????????????????vec_stack???????????free??????free?

?2.2.1

?2.2.2

?2.2.3

2.3 ???

??????????????glibc??malloc????ptmalloc?ptmalloc????????????????????????????????????????????????????????????????????????????New/Delete??O(1)??????????????????????????new?60?????????60???????60?????????????60?????????????????????????????????freeList????????usedList?freeList??queue?????usedList??vector?

?????????????????????2.3.1??Init?????????????capacity?pointer??capacity??????????????????pointer???????????Chunk???????Chunk?objectperchunk?T?????chunksize????????????????Init?????capacity??????????capacity?T????????objectperchunk?T??????????freelist??

??2.3.2?????????????NewObj?????freelist??????????????????????NewChunk??objectperchunk?T?????????????freeList??????

??2.3.3????????????DeleteObj??????????????????????????????usedList?????usedList??????????????????????deleteusedlistindex?????????????????freeList???????????????????????

??2.3.4?????????usedList???????????????????deleteusedlistindex == iterateindex???????????usedList???????????deleteusedlistindex?????iterateindex?????

?2.3.1

?2.3.2

?2.3.3

?2.3.4

2.4 ?????ptmalloc vs tcmalloc?

???????????????????malloc???????????ptmalloc?????????ptmalloc??????????????????????????????????????????????????A????????????????????????B???????????????A?????????????????ptmalloc?????chunk??8???????????????????????????

?????????tcmalloc???????tcmalloc?????????ThreadCache????????ptmalloc?????????????tcmalloc??????????????CentralCache?ThreadCache??????????CentralCache???ptmalloc??chunk??8??????????tcmalloc???chunk?????????????????????????????????ptmalloc?

???????????

3.1 ????????

???????????????????????????????????????M???c++?ifstream????????????????????????????????????????3.1.1???MATRIX_LEN?4096??????4096*4096byte??16M??3.1.1?byte????????2564ms??3.1.2???????????50ms?

?3.1.1

?3.1.2

?????????
????https://mp.weixin.qq.com/s/1WN9rA4yK6Wi2-BhQFIn5Q