Posts tagged ‘算法’

Degrafa的Bezier源码浅析(一)

先解释下Bezier曲线:

http://en.wikipedia.org/wiki/Bézier_curve

Degrafa是一套很强大的图形算法类库,并且开源,对Bezier曲线的绘制提供了很好的支持。说起Bezier曲线,其实就是Photoshop和flash里常用的钢笔工具啦,主要就是用来绘画路径或者绘画不规则图形。前者的应用领域非常广泛,比如使图形沿着路径运动,或者按路径不规则排列图形(具体一例就是扭曲的美术字布局)。这些都会用到Bezier曲线。

Degrafa提供的tutorial不是很完备,很多时候为了扩展应用不得不看源码。我这里只就Bezier相关的处理过程分析一下。

Degrafa下面的类非常之多,跟Bezier相关的主要有:

  • com.degrafa.geometry.splines.BezierSpline
  • com.degrafa.geometry.CubicBezier

两者都继承自com.degrafa.geometry.Geometry。很多图形库都有着类似的继承体系,Geometry作为一个基础的图形类,下面还有很多经过定义的不同种类的图形。

CubicBezier看字面意思,是一个三次贝塞尔曲线,事实上确实如此,它有四个点(start,end,2 control points)控制,其实也就是wiki上的那个图形

而BezierSpline跟真正的钢笔工具非常像,它由一系列点和control points来控制一整条曲线。这里最好看它的注释:

The BezierSpline can be used for drawing of a smooth curve through
multiple points, with some shape control over the curve via a tension
parameter. It may also be used for general path animation with tension
control, optional closed-path control, and velocity control
(arc-length parameterization).

乍看一下,它好像就是若干个CubicBezier的组合,其实关系不是很近。BezierSpline内部确实用到了CubicBezier对象(源码的第一行private var _bezier:Array),它是用来管理三次bezier曲线段的(BezierSpline包括很多的段)。

在使用BezierSpline曲线之前,需要提供一系列的点(钢笔工具的点类似)。使用到的property包括:

  • points
  • data

两者实质相同形式不同而已。

绘画曲线都使用draw方法,这个方法是由Geometry定义,并由它的子类重写的(典型的继承体系)。BezierSpline和CubicBezier都有类似的draw定义方式:

/**
* Begins the draw phase for geometry objects. All geometry objects
* override this to do their specific rendering.
*
* @param graphics The current context to draw to.
* @param rc A Rectangle object used for fill bounds.
**/
override public function draw(graphics:Graphics,rc:Rectangle):void{	

	//re init if required
 	if (invalidated) preDraw(); 

	//init the layout in this case done after predraw.
	if (_layoutConstraint) calculateLayout();

	super.draw(graphics, (rc)? rc:bounds);

}

preDraw在这个体系里非常重要,是用来在绘画之前计算各个点的位置,就像我们使用graphic那样定义好MoveTo和lineTo,所不同的这里会用到很多算法。与draw一样,preDraw在Geometry里定义在子类里重写,每个子类都有不同的方法。比如BezierSpline:

/**
* @inheritDoc
**/
   override public function preDraw():void{
   	if( invalidated ){

        	if(!points.length){return;}

        	_assignControlPoints();

        	//add a move to for the first item.
        	commandStack.length=0;

	//add a MoveTo at the start of the commandStack rendering chain
	commandStack.addMoveTo(points[0].x,points[0].y);

	var cubic:CubicBezier;

        //todo not sure were this extra one is coming from yet.
        //re:: - 1 on the count
        for( var i:uint=0; i<_bezier.length-1; ++i ){

        	cubic = _bezier[i];

        	commandStack.addCubicBezierTo(cubic.x0,cubic.y0,cubic.cx,
       	cubic.cy,cubic.cx1,cubic.cy1,cubic.x1,cubic.y1,1);

  	}

     		invalidated = false;
}
	    }

挖到这里,基本上快看到bezier算法在Degrafa里怎么实现的了,关键就是这个commandStack,字面意思:命令退栈,命令集合。

flash游戏中的数学问题

LongLongAgo,在做泡泡龙游戏的时候,发现数据结构的好处。使用树结构的数学模型可以清晰的描述逻辑处理方式。比如在判断是否有球掉落的时候,见下图,就可以用这样的数学语言描述:“对某个球而言,不存在一条路径到达root”。root就是最顶层。

泡泡龙

泡泡龙

如果这样的球存在的话,就说明它是“浮空”的,也就是说可以掉下来了。

这类的数学描述在很多领域都用过,记得flash的垃圾回收机制么,原来使用计数法来判断一个对象要不要被消灭,如果用在displayObject树结构里就不够了,因为它们可以相互引用,于是,用上面所说的数学描述就成了很好的补充,跟泡泡龙的原理类似,如果有一个displayObject不能到达root的话,它就脱离了显示树,就该被消灭,而不用管计数是多少。

回到泡泡龙的问题上来,一个被发射上来的球可以看成一个根节点,当它被打到一堆球当中的时候,一个树结构就形成了:以这个新球为根,周围的六个球为第一层子节点(可能某些是空,或者重复应用,需要剔除),然后使用广度优先或者深度优先遍历来查找“通往root的路径”,再加上些优化,就能实现这种数学描述,从而完成“掉落”这个游戏功能。

数学在flash游戏中无处不在。此乃往事,特此笔记。

山寨版AS3事件冒泡机制的实现

AS3实现了事件传递,分成三段Capture,target和bubble,其中bubble就是向树根传递。这个机制非常之经典和好用,可惜它只存在在基于DisplayObject的对象树中,其它时候只能把事件老老实实的从一个对象直接传递到另一个对象。

这次我来玩个有趣的。仿造AS3内置的机制来制作一个更加通用的冒泡框架,相信可以用很多用处(至少已经用在我的项目上了)。自己实现事件传递,让它支持任何事件任何数据结构(无论队列,还是树),甚至可以传递任何对象(而不仅限于事件对象)。其实bubble的过程不难,就是把一个对象(特例就是事件对象)在一个链表里自动传递,不断的向上抛,过程跟AS3的事件机制别无二致。为了能扩展,我准备了接口和初步的实现类:IBubbleDispatcher和CBubbleDispatcher。跟IEventDIspatcher和EventDispatcher一样吧。来看看代码。

package org.gl.geom.abstract 
{
	import flash.events.Event;
 
	/**
	 * ...
	 * @author Jonson
	 */
	public interface IBubbleDispatcher 
	{
		/**
		 * add to bubble tree
		 * 
		 * @param	child
		 * @param	father
		 */
		function registerAsMyChild(child:IBubbleDispatcher):void;
 
		/**
		 * dispatch event, then bubble
		 * 
		 * @param	event
		 */
		function bubble(event:Event):void;
 
		/**
		 * it's better to be override in subclass
		 * 
		 * @param	event
		 * @return	true means continue bubble
		 */
		function myBubbleEventHandler(event:Event):Boolean
	}
 
}
package org.gl.geom.abstract 
{
	import flash.events.Event;
 
	/**
	 * ...
	 * @author Jonson
	 */
	public class BubbleDispatcher implements IBubbleDispatcher
	{
		//////////////////////////////////////////////////
		// render event bubble
 
		private var __my_parent__:IBubbleDispatcher;
 
		/**
		 * add to bubble tree
		 * 
		 * @param	child
		 * @param	father
		 */
		public function registerAsMyChild(child:IBubbleDispatcher):void
		{
			if (child is BubbleDispatcher)
			{
				(child as BubbleDispatcher).__my_parent__ = this;
			}
		}
 
		/**
		 * dispatch event, then bubble
		 * 
		 * @param	event
		 */
		public function bubble(event:Event):void
		{
			if (__my_parent__)
			{
				var neve:Event = event.clone();
				if (__my_parent__.myBubbleEventHandler(neve))
				{
					__my_parent__.bubble(neve);
				}
			}
		}
 
		/**
		 * it's better to be override in subclass
		 * 
		 * @param	event
		 * @return	true means continue bubble
		 */
		public function myBubbleEventHandler(event:Event):Boolean
		{
			//it's better to be override in subclass
			return true;
		}
	}
}

为了便于理解,我这里与AS3内置的EventDispatcher做些比较。

  • 把CBubbleDispatcher做父类(和EventDispatcher一样)。
  • 使用registerAsMyChild注册叶子对象(类似于addChild和addEventListener的组合,先把叶子对象作为当前对象的child,然后注册监听),这样的话,叶子抛出的事件对象就能被父亲对象处理了,或者再向上抛。
  • 使用bubble发出事件(相当于dispatchEvent)。
  • 子类重写myBubbleEventHandler来处理事件,返回true说明继续向上传递(类似于stopPropagation功能),如果不需要处理就不必重写。这样设计的好处是,不需要根据不同的Event type而写上很多很多的addEventListener。

补个小例子

class parent1Class extends CBubbleDispatcher
{
      public function parent1Class(){this.registerAsMyChild(_child);}
      private var _child:parent2Class = new parent2Class();
}
class parent2Class extends CBubbleDispatcher
{
      public function parent2Class(){this.registerAsMyChild(_child);}
      private var _child:childClass = new childClass();
}
class childClass extends CBubbleDispatcher
{
      public function try():void{this.bubble(new Event("UP"))};
}

Flex源码学习之mx.utils.*

我承认这个标题有点标题党的味道。其实我的意思是想说,flex framework里有些code并不是依赖于framework的,怎么说呢,它们是纯算法,是数据处理,而并没有用到其它的flex framework class已经一些,比如metadata特性(有也可以改掉)。比如下面要提到的mx.utils.ColorUtil,还有StringUtil。于是我们就可以把它们提炼出来,用在普通AS3/Flash project当中,而不需要依赖,导入flex framework。

flex sdk已经开源了,进入sdk folder查找ColorUtil。来看看它处理brightness的算法

/**
 *  Performs a scaled brightness adjustment of an RGB color.
 *
 *  @param rgb Original RGB color.
 *
 *  @param brite The percentage to brighten or darken the original color.
 *  If positive, the original color is brightened toward white
 *  by this percentage. If negative, it is darkened toward black
 *  by this percentage.
 *  The range for this parameter is -100 to 100;
 *  -100 produces black while 100 produces white.
 *  If this parameter is 0, the RGB color returned
 *  is the same as the original color.
 *
 *  @return New RGB color.
 */
public static function adjustBrightness(rgb:uint, brite:Number):uint
{
	var r:Number;
	var g:Number;
	var b:Number;
 
	if (brite == 0)
		return rgb;
 
	if (brite < 0)
	{
		brite = (100 + brite) / 100;
		r = ((rgb >> 16) & 0xFF) * brite;
		g = ((rgb >> 8) & 0xFF) * brite;
		b = (rgb & 0xFF) * brite;
	}
	else // bright > 0
	{
		brite /= 100;
		r = ((rgb >> 16) & 0xFF);
		g = ((rgb >> 8) & 0xFF);
		b = (rgb & 0xFF);
 
		r += ((0xFF - r) * brite);
		g += ((0xFF - g) * brite);
		b += ((0xFF - b) * brite);
 
		r = Math.min(r, 255);
		g = Math.min(g, 255);
		b = Math.min(b, 255);
	}
 
	return (r << 16) | (g << 8) | b;
}

是不是很优雅。Adobe的精英工程师创造出来的,效率及简介性肯定可以保证,况且开源了,为啥不好好利用呢。flex code里有很多好货可以发掘。

递归调用处理连续的异步操作

今天来总结一种个人常用的处理方式。

案例:

在循环语句中处理一些操作,很可惜,操作都是异步的(比如向服务器访问,必须要用事件等待回应)。而且,必须要求是上一步完成后才能进行下一步。我们知道,AS是不能阻塞线程的。所以用循环语句不行。

我的办法:

准备一个方法,如function(index:int, maxlength:int, …)。在这个function里执行异步操作,等拿到结果后再调用function(index+1, maxlength),形成递归调用,当然执行异步操作之前必须检测index<=maxlength,要让循环结束嘛。注意到…了吗,可能你的操作还需要一些别的变量,如果你需要的变量特别多的话,我还是建议用内嵌函数,用code说话吧:

var func:Function = function(index:int, maxlength:int):void
      {
            ...
      }
 
//start
func(0, maxlength);

它就能利用内嵌函数的特性,来直接取用你的类变量或者函数内变量了(局部变量)。AS3当然会有这种特性,动态语言都有类似特性。

C++数字转字符串

自己写了个算法,long转char数组。好久没有做c++的算法,生疏了,感觉又回到了考计算机三级的时候。

	LONG num = sampleActualLen;
	char strnum[20] = {0};
	char *pstrnum = strnum;
	pstrnum += 20;
	while (num>0)
	{
		pstrnum--;
		*pstrnum = (char)(num%10+'0');
		num /= 10;
	}
	int strnum_len = 20 - (pstrnum-strnum)/sizeof(char);

char *strnum和strnum_len是最后的数组指针和长度。不过我设了最大长度20,一般的数字够了吧。

AS3实现来自java的几种算法

今天复习和梳理了一下自己写的序列号算法。提炼了几种有普遍意义的算法
十六进制字符转Number

private function charToInt(s:String):Number
{
	if(s.length&gt;1)
	{
		return -1
	}
	else
	{
		if(isNaN(Number(s)))
		{
			s = s.toUpperCase();
			switch(s)
			{
				case "A":
					return 10;
				case "B":
					return 11;
				case "C":
					return 12;
				case "D":
					return 13;
				case "E":
					return 14;
				case "F":
					return 15;
				default:
					return -1;
			}
		}
		else
		{
			return Number(s)
		}
	}
}

十六进制数字字符串转Number(这次是一串数字哦比如”BC1A”)

private function parseInt(s:String):Number
		{
			var result:Number = 0;
			var i:Number = 0;
			var max:Number = s.length;
			var limit:Number = -Number.MAX_VALUE;
			var multmin:Number = limit/16;
			var digit:Number = 0;
 
			if(max>0)
			{
				if(i<max)
				{
					digit = charToInt(s.charAt(i++));
					if(digit<0)
					{
						throw new NumberFormatException("unsupported number")
					}
					else
					{
						result = -digit
					}
				}
 
				while(i<max)
				{
					digit = charToInt(s.charAt(i++));
					if(digit<0)
					{
						throw new NumberFormatException("unsupported number")
					}
					if(result<multmin)
					{
						throw new NumberFormatException("too small")
					}
					result *= 16;
					if(result < limit+digit)
					{
						throw new NumberFormatException("too small2")
					}
					result -= digit;
				}
			}
			else
			{
				throw new NumberFormatException("unformated")
			}
 
			return -result
		}

hash算法

private function hashcode(s:String):int
{
	var hash:int = 0;
	for(var i:int=0 ; i<s.length ; i++)
	{
		hash = 31*hash + s.charCodeAt(i)
	}
	return hash;
}