?????DOOM3????????????

??

?/??

?????????? DOOM 3 ??????????????????? (2006) ???????????????????????????? DOOM3 BFG ??????????????????

??[?] DOOM3 BFG ? DOOM3 ????????

????DOOM3 ????

??????

??DOOM3 ???? (2004) ??????????????????? 640*480 ??????? 20fps????? DOOM 3 BFG ????? 2012 ????? 1280*720 ???????? 60 fps ??????????? 1/3 ????? 3 ??????????

???????????? CPU ?????????????????????? (? DOOM3 ??????)?GPU ???????????????????? (??? coarse Z-Cull / Hierarchical-Z ??? Stencil Shadow Volumes)????????????????????????????????????????????????????

??????

??? DOOM3 ? DOOM3 BFG ?????????? (cache thrashing)??? DOOM ????????????????????????????????????

??DOOM3 ???????�????????�??????????????????????????????? (???????????????????) ??????????????????????? (streaming programming model) ([?]??????????? functional ?????)?

????????????? (visible meshes and shadow volumes) ????? GPU ?????? GPU ?????????????? CPU ???????????????????? shadow volume ? light volume ???????????????????? Mars City 1 ??????? shadow volume / light culling ?????? 6MB ???????? 2.5MB ???????????????? (write-combined buffer) ????????????????????????????????????????????????????? x86 ???????? Cell SPU ??? (PS3) ?????????????? SSE4.1 ????? _mm_stream_load_si128() ???????????????????????????????????????????????????????????????

?????????�???+??�

??????????CPU????????????????????????????????????? DOOM3 ?????????????????????????????? shadow volume ?????? DOOM3 BFG ???????????????????????????????(? GPU ?) ??? mesh ?????????????????�????�????????????????????????????????????????????????????????

??1.??????????????????? GPU ??????????????????????

??2.??????????????????????????????????????????? 1:n?????????????

??3.???????????????????????????

??DOOM3 BFG ? shadow volume ??????(????????????)????????????????????????????? 7 ????2*2 ?????? shadow volumes ???????1 ??????????????? light surfaces ????????????????7 ??????? DOOM3 ??? 1 ?????????????????????????????????

????????? functional ???????????????????????????????????????????? skinned version???????????????????????????????????? shadow volumes ????????????

????-?????????

???????????????????????? cache-unfriendly ????????????????????????????????????????????????????????????????????? 'idList' ?????? resizable heap array?? vector ??????

????

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

??�if these threads touch a significant amount of memory then cache thrashing may occur while many CPUs are poorly equipped to avoid large scale cache pollution. Without additional instructions to manage or bypass the cache, a shared cache between all CPU cores can result in less than ideal performance.

??�various data structures that exhibit poor performance on today's hardware. These data structures tend to result in poor memory access patterns and excessive cache misses.

????DOOM/Quake I/II/III ???????

???????

??????????????????????????????????? (consistency, responsiveness, bandwidth and latency requirements)

??�Multiplayer gaming is about shared reality.�

??FPS ????????????????????????????????? (entities) ?????????????????????????????????????

??�Networking in first person shooters is all about synchronizing the state of multiple copies of the same game entities such that all players experience the same changes and events in the virtual environment.�

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

??P2P ?? (DOOM)

??DOOM (1994) ??????????? P2P ??????????????? (move/turn/use/fire, etc.) ?? 35 ? (???? tick command) ????????????????????????? tick command?????????????????? tick command ??????????????????????????????? (???????????????????) ?????????????

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

??1.?????????????????????????(????????????)???????????????????????????????????????????????????????????????????????????????????????????????????

??2.????????????????????????????????????????????? (??????)?

??3.????????????????????????????????????????????????

??4.???????????????????????

??5.????????? tick command????????????? (???????????) ?????????????

??6.????????????????????????

??Packet Server (??????)

????????? DOOM ????????? Packet Server???????? tick command??????????????????????? (???????) ?????????????????????????????????????????????????????????????

??Client Server (Quake I/II/III)

??Quake I/II/III ???????? C/S ?? (1996)???????????????????????????????????????????????????????????????????????????????? (10-20Hz) ??????????????????????? (interpolates between, or extrapolates from the last two snapshots)?

????????(????????Quake 1?)????????????????????????????????????????????Quake 3??????????????????????????????????????????????????????????????????????????????�???????�????

• "Quake III Arena ??????(???)"
  

????????

??????????????????????????????????? roundtrip ??????????????????????? ????????????????????????????????? interpolate/extrapolate????????????? (????) ????????????????(????????????) ?? C/S ????????????????????????????????????????????????????????????

??????????????? (??? server ???????? dedicated ??)?????????????????????????????????????????????????????????????????????????????????????

???????????

??????????????????????? (lag compensation)????????? (????????) ?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? ??????????????????????????????????????????????

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

??Q3 ??????????? ("game code") ????????????? ("client game code") ????????????????????????????? (???????????????)????????????????????????????????????????? Q3 ??????????????????????? exe??????????? game code ????????

????/??????

??????????????????????????????? interpolate/extrapolate?????????????(??????????) ?????????????????????????????????????????????????????? slerp ?????

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

??Quake III ???? PVS ?????????????????????????????????? (delta compressed relative to the entity states from a previous snapshot) ????????????????? PVS ???? delta ????????????????????????

??????????????????Quake 3????????????????????????????????????????????????????????????????????????????Delta???

• "Quake III Arena ??????(???)"
  

???????Q3 ?????????????????????????????????????????

????DOOM3 ????

????

??????????????????????????? PVS ???????????

??C/S ???

??Doom3 ???????????????????????????????????

??1.?????????????? (system-wide deterministic)

??2.????????????????????? 60 fps ?????

??C/S ???

?????? 10-20 Hz ???????????????????? rtt ????????????????????????�???�??????????????????????????????????

??????? (Prediction at the client with a snapshot rate at 20Hz and a ping of around 80 milliseconds)

??????????? (input per second) ?????????? (60 Hz)????????????????????????????????????????????????????????????????????????????????????????????????

??? Quake 3 ??????????????????????????????? (????????? 100% ????)??????? Q3 ??????????????????????????????????????????????????????????????????? (dead reckoning)???????????????????????Quake 3 ? bot ???????????????????????????????????? (??? RL) ???????????(Q3 bot ??????????????????????????)

??? Quake 3 ???Doom 3 ??????????????????/???????????????????????????????? (?????) ????????

????

???? UDP ???? reliable / unreliable ?? (???????)

??????????????? TCP ?????????????????????????????????

??Doom 3 ??????????? UDP ??? FPS ????

???????

?????????????????? reliable & unreliable ??? (??????)??????? (c2s) ??? (s2c) ?????????????????????????

?????????????????????????? (unreliable stream) (?? 10-20Hz ??????????????)???????? (piggy back) ?????????? (????)??????????????????????????????????????ack ?????? (ack ?????????? unreliable stream) ????????????????(??1:1???)???????????????????????????? (the message channel guarantees that a reliable message arrives before the first next unreliable messages comes through)

????????????????????????????3-4? (????????????)??????????????????? timeout ??????????????????? ack ???????????????

??Unreliable Message Headers

??????????????????????? (Snapshots) ??????????? (User Commands)?????????? unreliable message ???(message header ?????)

??????

• 32 ? game id ??????????? id?????????????
• 8 ?? message type ????????????
  

??????

• ?? seq id ??????????????? (?? ack)?unreliable message ?????? ack ??????????????????????????? seq id ??????????????
• game id ????????????????????????????????????????????????????
• ??? seq id ?????? (delta compression)
• ???? message type?
  

???? (snapshots)

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

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

• ??? (seq id)
• ??? (frame id)
• ??? (frame time)
• ????????? (client ahead time, ??????????????????)
  

??????????? (???????????)?

• entity states ??????????????
• pvs bit string ? pvs ????????? (??????????????)
• pvs ?????????
• ?????????
  

?????? (User Commands)

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

• ????????????
• ??????????????????
• ????? user command ???????????????????
  

????

??Bit Packing

• ??????????
• ? Health (HP) ??? 32 ???????? 0-100????? 7 ?????
• ????????????????? (???????????????) ???????
  

?????? (Delta Compression)

??1.??????????????????????? 0 (1 bits) ??????? 1 (1 bits) + ?????? (bit packed)

??2.?????????

??o?????????

??o???????????????? (common base)

??o????????? pvs ???/????

??3.pvs ?????

??o???? 1 bit ? 4096 ???????? 512 ??

??o??????? pvs ?????????????? 32 bits

??o???????????? pvs??? 0 (1 bits)

??o?? pvs ???????4096 ?????? 16 ??

??????? User Commands ??? ack ????????????????????????????? ack ?????????? reliable message ??????????????????? reliable message ???????????????? ack ?????????????????????????????????????????????????

?????? (0-compressor)

??????????????? 0 (????)????????????????? 0 ??????

?????? 3 ??????????? 0 ?????????????????????????????? (3 bits) ????? (3 bits)

???????? 4:1???????????? 3 ?????????????

???????

??000'000'000'010'000'000'000'000'110'000'000'000'000'000

???????

??000'011'010'000'100'110'000'101

??????????? 14:8?

???????????????????????????????????????????????????????? 0?

????

• bit packing: 10-15%
• delta compression: 90%+
• zero-compressing: 15-50%
  

?????????

• ?????????????????????????????????????????????????????????
• ???? reliable ??????????????? (???????) ???? unreliable ?????
• ?????????????????????????????????????
• ???????????????
  

??o????????????????? (?????????)

??o????????????? (???????) ????????

• ???????????????????????????????????????? (LOD-syncing)
• ?????????????????????????????? (?????)
  

???????????NGUI???????????NData

????

????