[Tech Blog]横版游戏中的快速碰撞检测
Autukill 发表于 2014-05-19 11:50:41 2930

本帖最后由 Autukill 于 2014-6-3 23:22 编辑

原帖:https://www.yoyogames.com/tech_blog/7
论坛:http://www.gamemake.org/forum.php?mod=viewthread&tid=384&page=1#pid2374
Wiki:http://wiki.gamemake.org/index.php?doc-view-6

说明:并非对原文的完整翻译,而是提取重点。

这是碰撞相关知识的第二篇,第一篇:精确碰撞检测的危害
[hr]

在第一篇中,我们讲到了不要滥用内置函数,这里再提出一些: [font=Arial]move_outside_XX 、move_bounce_XX[/font]等,原因呢就在第一篇中。
说到横版游戏([backcolor=rgb(252, 252, 252)]platform games[/backcolor]),不得不提那些年的游戏机:[backcolor=rgb(252, 252, 252)]NES, C64, Megadrive, SNES,他们的横版游戏碰撞系统都用到同一种方法:[/backcolor][backcolor=rgb(252, 252, 252)]tilemaps(图块法)。[/backcolor]
[align=center][attach]491[/attach][/align]

[align=left]此图块跟GM中的图块不一样哦。举个例子:在上图中,所有的(土色)地砖,包括玩家角色脚接触的那种砖块,他们的大小和位置都是统一的,这样方便存储和检测。GM中仅仅是Background或者Sprite,并没有碰撞的信息。所以,下面就让我们来实现这种图块吧。[/align]

[align=left]Demo:http://pan.baidu.com/s/1eQIeo3g ,修改了官方的Demo.[/align]
[align=left]GM版本为GMS1.2,此法适用于横版游戏,并且GM中的碰撞贴图资源都为固定大小。[/align]
[align=left]运行此DEMO,在GMS输出窗口中可见如下,一些由“1”和“_”组成的和游戏中的地形一样的文字矩阵,其中的"1"表示有障碍物,而"_"表示无障碍(你也可以,用2来表示草地,3表示水路)。[/align]
[align=center][attach]492[/attach][/align]

[align=left]那这个文字矩阵是怎么得到的呢?[/align]
[align=left]你可以在Demo脚本中找到相关细节。原理就是房间初始时,用For函数扫描整个房间内的贴图位置(把笛卡尔坐标转换成栅格坐标),并存储在一维数组中(数组的检索是最快的),对象移动的过程中,检索此数组即可,抛弃那些“笨重”的内置函数。[/align]

[align=left]如果对象嵌入了障碍(图块)中,怎么办?[/align]
这里,我们先提进制的知识。1.对于十进制2的N次幂数与二进制数存在下面的映射关系:
[table=50%]
[tr][td] 二进制[/td][td] 十进制[/td][/tr]
[tr][td] 1 [/td][td] 1[/td][/tr]
[tr][td] 10[/td][td] 2[/td][/tr]
[tr][td] 100[/td][td] 4[/td][/tr]
[tr][td] 1000 [/td][td] 8[/td][/tr]
[tr][td] 10000 [/td][td] 16[/td][/tr]
[/table]

2.我们可以对二进制数进行移位操作,比如左移(使用运算符<<,尖角指向左侧)、右移(使用运算符>>,尖角指向右侧),二进制数1 左移2位后,得100,100右移2位后,又得到1.


3.二进制数还可以进行:与、或、非操作

[align=left]如果,我们随意组合数字,可以得出一些映射关系[/align][table=465]
[tr][td] 二进制[/td][td] 十进制[/td][/tr]
[tr][td] 110 [/td][td] 6[/td][/tr]
[tr][td] 1101[/td][td] 13[/td][/tr]
[tr][td] 11[/td][td] 3[/td][/tr]
[tr][td] 1001[/td][td] 9[/td][/tr]
[tr][td][font=Helvetica Neue, Helvetica, Arial, sans-serif][backcolor=rgb(252, 252, 252)] 1111[/backcolor][/font][/td][td] 15[/td][/tr]
[/table]

[align=left]如果,我们把二进制数中第一位后面的数都改为0,会发生什么?[/align][align=left][table=50%]
[tr][td] 前[/td][td] 后[/td][/tr]
[tr][td] 110 (6)[/td][td] 100 (4)[/td][/tr]
[tr][td] 1101 (13)[/td][td] 1000 (8)[/td][/tr]
[/table][/align][align=left]太好了,我们高效的对偏移数据进行了修正。:)[/align]
[align=left]如果,我们的图块是32 X 32 ,玩家的画布坐标y值为68(如下图),我们的角色嵌入到了障碍物中,我们知道,正确的y坐标为64。为了修正y坐标,我们同样采用二进制操作的方法。[backcolor=rgb(252, 252, 252)][font=Helvetica Neue, Helvetica, Arial, sans-serif]1001000 (68) & [/font]$ffffffe0[font=Helvetica Neue, Helvetica, Arial, sans-serif]= %1000000 (64),(你可以在DEMO中找到此运算细节)[/font][/backcolor][/align][align=center][attach]493[/attach][/align]
[align=left]可能有人问$ffffffe0 是什么?[/align][align=left]
[/align][align=left]
Quote[align=left]$ffffffe0(16) = 11111111111111111111111111100000(2) = ~ ( 32 ) +1 (10)= -32(10)[/align][align=left]占用内存大小为双字(4[font=宋体]个字节[/font][font=Arial]/32[/font][font=宋体]位[/font])[/align][align=left]"~"[font=宋体]是[/font]按位取反([font=宋体]计算器中符号为“[/font][font=Tahoma]Not[/font][font=宋体]”[/font][font=Tahoma])[/font][font=宋体]。[/font][/align][align=left]负数在内存中存储都是用补码,即按位取反后加[font=Tahoma]1[/font][font=宋体]。[/font]

32,[font=宋体]原码为[/font][font=Tahoma]0 [/font][font=宋体]——————————————[/font][font=Tahoma]00100000[/font][/align][align=left] ~ 32 ,[font=宋体]原码为[/font][font=Tahoma]11111111111111111111111111011111[/font][/align][align=left]~ 32 +1,[font=宋体]原码为[/font][font=Tahoma]11111111111111111111111111100000[/font]

~ 32 +1 [font=宋体]十六进制就是 [/font][font=Tahoma]FF FF FF E0[/font][font=宋体],换成十进制就是[/font][font=Tahoma]4294967264[/font][/align][align=left]综上原理说明可知:[/align][align=left](68 & $ffffffe0) [font=宋体]就是[/font][/align][align=left] 0000 0000 0000 0000 0000 0000 0100 0100[/align][align=left] & 1111 1111 1111 1111 1111 1111 1110 0000[/align][align=left]————————————————————————————[/align][align=left] 0000 0000 0000 0000 0000 0000 0100 0000 = 64[/align][align=left]你可以把[font=Tahoma]68[/font][font=宋体]换成[/font][font=Tahoma]33[/font][font=宋体],[/font][font=Tahoma]129[/font][font=宋体],都可以快速修正偏移变量为 [/font][font=Tahoma]32,128[/font][/align]

[/align][align=left][font=Helvetica Neue, Helvetica, Arial, sans-serif][backcolor=rgb(252, 252, 252)]以上,我都是运行计算器 ,选择 程序员模式,双字,进行的计算。(这里有个讨论:[/backcolor]http://gmc.yoyogames.com/index.php?showtopic=544698[/font][backcolor=rgb(252, 252, 252)])[/backcolor][/align][font=Helvetica Neue, Helvetica, Arial, sans-serif][backcolor=rgb(252, 252, 252)]
[/backcolor]
[/font][font=Helvetica Neue, Helvetica, Arial, sans-serif][backcolor=rgb(252, 252, 252)]当然,如果二进制不会,我们还是用老办法 floor(68/16) * 4 = 64 :)[/backcolor][/font]




最新回复 (6)
  • Autukill 发表于 2014-05-23 08:41:28
    0 2
    这里还有深入内容:
    Bit Twiddling Hacks(位操作的技巧):http://graphics.stanford.edu/~seander/bithacks.html
  • 红色激情 发表于 2014-05-23 10:27:19
    0 3
    位修正比“floor(68/16) * 4 = 64”效率高多少?
  • Autukill 发表于 2014-05-23 11:06:29
    0 4
    本帖最后由 Autukill 于 2014-5-24 20:15 编辑

    Quote红色激情 发表于 2014-5-23 10:27
    位修正比“floor(68/16) * 4 = 64”效率高多少?

    效率高多少,我没有进行比较。
    帖子(An introduction to Binary:https://www.yoyogames.com/tech_blog/58)有个例子:


    QuoteAs a very simple example, in the past multiplying by 32 might have taken several CPU cycles to execute, while a simple binary operation to do the same thing would have taken only 1. As machines have gotten more complex, they have also reduced the time many complex instructions take to run so that now, a 32x32 bit multiply might well only take 1 cycle - same as the binary operator.

    [font=Helvetica Neue, Helvetica, Arial, sans-serif][backcolor=rgb(252, 252, 252)]以一个简单的例子来说,过去某个数32次幂的运算,将花费几个CPU周期,然而使用简单的位操作仅需一个周期。随着现代机器的复杂化,位操作取到减少复杂命令执行时的消耗的作用。对于(32X32) bit 的乘法运算,[/backcolor][/font][backcolor=rgb(252, 252, 252)]位操作[/backcolor][backcolor=rgb(252, 252, 252)]很可能仅占用一个CPU周期。[/backcolor]

    [font=Helvetica Neue, Helvetica, Arial, sans-serif][backcolor=rgb(252, 252, 252)]当然,这篇文章的作者以移动平台为中心的。[/backcolor][/font]
    [font=Helvetica Neue, Helvetica, Arial, sans-serif][backcolor=rgb(252, 252, 252)]
    [/backcolor]
    [/font]
    [font=Helvetica Neue, Helvetica, Arial, sans-serif][backcolor=rgb(252, 252, 252)]百度百科 ([/backcolor][/font]位操作http://baike.baidu.com/view/8430897.htm)
    [font=Helvetica Neue, Helvetica, Arial, sans-serif]定义中有句话:[/font][font=arial, 宋体, sans-serif]在现代架构中, 情况并非如此:位运算的运算速度通常与[/font][font=arial, 宋体, sans-serif]加法[/font][font=arial, 宋体, sans-serif]运算相同(仍然快于[/font][font=arial, 宋体, sans-serif]乘法[/font][font=arial, 宋体, sans-serif]运算).[/font][backcolor=rgb(252, 252, 252)]
    [/backcolor]
    Quote(32X32) bit举个例子 就是11111111111111111111111111111010 (32bits) * 11111111111111111111111111111010 (32bits)

    [backcolor=rgb(252, 252, 252)]
    [/backcolor]






  • 夏也 发表于 2014-05-23 07:57:12
    0 5
    LZ的帖子都十分有营养~多谢~
  • 红色激情 发表于 2014-05-24 06:25:21
    0 6
    QuoteAutukill 发表于 2014-5-23 11:06
    效率高多少,我没有进行比较。
    帖子(An introduction to Binary:https://www.yoyogames.com/tech_blog/5 ...


    涨姿势了。谢啦