人工智能、数理算法

oraclelang

如果你用上面的信息分别对你做的md5算法实例做测试，最后得出的结论和标准答案完全一样，那我就要在这里象你道一声祝贺了。要知道，我的程序在第一次编译成功的时候是没有得出和上面相同的结果的

oraclelang

MD5的安全性

　　md5相对md4所作的改进：

　　　1. 增加了第四轮；

　　　2. 每一步均有唯一的加法常数；

　　　3. 为减弱第二轮中函数g的对称性从(x&y)|(x&z)|(y&z)变为(x&z)|(y&(~z))；

　　　4. 第一步加上了上一步的结果，这将引起更快的雪崩效应；

　　　5. 改变了第二轮和第三轮中访问消息子分组的次序，使其更不相似；

　　　6. 近似优化了每一轮中的循环左移位移量以实现更快的雪崩效应。各轮的位移量互不相同。

oraclelang

高级碰撞检测技术　第一部分
Advanced Collision Detection Techniques

这文章原载于Gamasutra，共有三部分。我想将它翻译，请大家指教。

http://www.gamasutra.com/features/20000330/bobic_01.htm
http://www.gamasutra.com/features/20000330/bobic_02.htm
http://www.gamasutra.com/features/20000330/bobic_03.htm

oraclelang

自从电脑游戏降临以来，程序员们不断地设计各种方法去模拟现实的世界。例如Pong（著名的碰球游戏），展示了一个动人的场面（一个球及两根摆绳）。当玩家将拽住摆绳移动到一定高度的，然后放开球，球就会离开玩家向对手冲去。以今天的标准，这样的基础操作也许就是原始碰撞检测的起源。现在的电脑游戏比以前的Pong复杂多了，而且更多是基于3D的。这也使3D碰撞检测的困难要远远高于一个简单的2D Pong。一些较早的飞行模拟游戏说明了糟糕的碰撞检测技术是怎样破坏一个游戏。如：当你的飞机撞到一座山峰的时候，你居然还可以安全的幸存下来，这在现实中是不可能发生的。甚至最近刚出的一些游戏也存在此类问题。许多玩家对他们喜爱的英雄或是女英雄部分身体居然可以穿过墙而感到失望。甚至更坏的是玩家被一颗没有和他发生碰撞关系的火箭击中。因为今天的玩家要求增加唯实论的要求越来越高，我们游戏开发者们将尽可能在我们的游戏世界做一些改进以便接近真实的世界。

oraclelang

Since the advent of computer games, programmers have continually devised ways to simulate the world more precisely. Pong, for instance, featured a moving square (a ball) and two paddles. Players had to move the paddles to an appropriate position at an appropriate time, thus rebounding the ball toward the opponent and away from the player. The root of this basic operation is primitive(by today’s standards) collision detection. Today’s games are much more advanced than Pong, and most are based in 3D. Collision detection in 3D is many magnitudes more difficult to implement than a simple 2D Pong game. The experience of playing some of the early flight simulators illustrated how bad collision detection can ruin a game. Flying through a mountain peak and surviving isn’t very realistic. Even some recent games have exhibited collision problems. Many game players have been disappointed by the sight of their favorite heroes or heroines with parts of their bodies inside rigid walls. Even worse, many players have had the experience of being hit by a rocket or bullet that was “not even close” to them. Because today’s players demand increasing levels of realism, we developers will have to do some hard thinking in order to approximate the real world in our game worlds as closely as possible.

oraclelang

2 …………………………………………………………………………………………………
这篇碰撞检测的论文会使用一些基础的几何学及数学知识。在文章的结束，我也会提供一些参考文献给你。我假定你已经读过Jeff Lander写的图形教程中的碰撞检测部分(“Crashing into the New Year,” ; “When Two Hearts Collide,”; and “Collision Response: Bouncy, Trouncy, Fun,” )。我将给你一些图片让你能快速的联系起核心例程。我们将要讨论的碰撞检测是基于portal-based 及BSP-based 两种类型的引擎。因为每个引擎都有自己组织结构，这使得虚拟世界物体的碰撞检测技术也不尽相同。面向对象的碰撞检测是使用得比较多的，但这取决于你的现实可实性，就想将引擎分成两部分一样。稍后，我们会概述多边形碰撞检测，也会研究如何扩展我们的弯曲物体

oraclelang

This article will assume a basic understanding of the geometry and math involved in collision detection. At the end of the article, I’ll provide some references in case you feel a bit rusty in this area. I’ll also assume that you’ve read Jeff Lander’s Graphic Content columns on collision detection (“Crashing into the New Year,” ; “When Two Hearts Collide,”; and “Collision Response: Bouncy, Trouncy, Fun,” ). I’ll take a top-down approach to collision detection by first looking at the whole picture and then quickly inspecting the core routines. I’ll discuss collision detection for two types of graphics engines: portal-based and BSP-based engines. Because the geometry in each engine is organized very differently from the other, the techniques for world-object collision detection are very different. The object-object collision detection, for the most part, will be the same for both types of engines, depending upon your current implementation. After we cover polygonal collision detection, we’ll examine how to extend what we’ve learned to curved objects.

oraclelang

重要的图片
编写一个最好的碰撞检测例程。我们开始设计并且编写它的基本程序框架，与此同时我们也正在开发着一款游戏的图形管线。要想在工程结束的时候才加入碰撞检测是比较不好的。因为，快速的编写一个碰撞检测会使得游戏开发周期延迟甚至会导致游戏难产。在一个完美的游戏引擎中，碰撞检测应该是精确、有效、而且速度要快。这些意味着碰撞检测必须通过场景几何学的管理途径。蛮力方法是不会工作的 — 因为今天，3D游戏每幀运行时处理的数据量是令人难以置信的。你能想象一个多边形物体的检测时间。
在一个完美的比赛发动机,碰撞察觉应该是精确,有效,并且很快的。这些要求意味着那碰撞察觉必须仔细到景色被系住几何学管理管道。禽兽力量方法嬴得’t 工作—今天’s 3D 比赛每框架处理的数据的数量能是介意犹豫。去是你能核对对在景色的每另外的多角形的一个物体的每多角形的时间

oraclelang

The Big Picture
To create an optimal collision detection routine, we have to start planning and creating its basic framework at the same time that we’re developing a game’s graphics pipeline. Adding collision detection near the end of a project is very difficult. Building a quick collision detection hack near the end of a development cycle will probably ruin the whole game because it’ll be impossible to make it efficient. In a perfect game engine, collision detection should be precise, efficient, and very fast. These requirements mean that collision detection has to be tied closely to the scene geometry management pipeline. Brute force methods won’t work — the amount of data that today’s 3D games handle per frame can be mind-boggling. Gone are the times when you could check each polygon of an object against every other polygon in the scene.

oraclelang

让我们来看看一个游戏的基本循环引擎。（Listing 1）
http://www.gamasutra.com/features/20000330/bobic_l1.htm
这段代码简要的阐明了我们碰撞检测的想法。我们假设碰撞没发生并且更新物体的位置，如果我们发现碰撞发生了，我们移动物体回来并且不允许它通过边界（或删除它或采取一些另外预防措施）。然而，因为我们不知道物体的先前的位置是否仍然是可得到的，这个假设是太过分简单化的。你必须为这种情况设计一个解决方案（否则，你将可能经历碰撞而你将被粘住)。如果你是一个细心的玩家，你可能在游戏中会注意到，当你走近一面墙并且试图通过它时，你会看见墙开始动摇。你正在经历的，是感动运动返回来的效果。动摇是一个粗糙的时间坡度的结果(时间片)。
Let’s begin by taking a look at a basic game engine loop (Listing 1). A quick scan of this code reveals our strategy for collision detection. We assume that collision has not occurred and update the object’s position. If we find that a collision has occurred, we move the object back and do not allow it to pass the boundary (or destroy it or take some other preventative measure). However, this assumption is too simplistic because we don’t know if the object’s previous position is still available. You’ll have to devise a scheme for what to do in this case (otherwise, you’ll probably experience a crash or you’ll be stuck). If you’re an avid game player, you’ve probably noticed that in some games, the view starts to shake when you approach a wall and try to go through it. What you’re experiencing is the effect of moving the player back. Shaking is the result of a coarse time gradient (time slice).