分类目录归档：编程

Snake Challenge算法思路

发表评论

Snake Challenge是GuruDigger推出的一个活动。游戏脱胎于经典的贪吃蛇，双方用程序控制snake，在规定步数内吃到最长的为获胜方。该平台的SDK以及范例放在BitBucket上，部署好的比赛平台在 http://pythonvsruby.org 。比赛平台上4四个房间，可以任意选择一个房间开始比赛（访问速度好像很悲催，我的snake一直掉线）。

我的AI程序在：https://bitbucket.org/vicalloy/snake-challenge 对应的目录为：snake-challenge/examples/vicalloy

下面简单的介绍一下主要的算法思路：

地图的表示

简单的说就是将地图上的障碍物实物等标记出来，这是整个程序中最简单的一部分。地图可以简单的用二维数组（python中实际为list）表示，数组中的值代表地图上的物品，如 0：BLANK 10:EGG 20:WALL。

查找目标食物

选择哪个食物

服务端会返回所有的egg和gem信息，要找到食物是很容易的，真正的问题是具体要选那个。

我们当然希望去吃最近的食物，或扎堆的食物（虽然远点，不过食物多），只是在真实环境下问题会非常多。如何才是最近，有些食物虽然看起来近，但算上绕过障碍物的距离就不近了。扎堆的食物看起来不错，问题是你没等你到那里，食物已经被别人给吃光了。如果想做到最优，那绝对不是一件容易的事。

既然不管怎么做都很难做到最优，倒不如简单些，直接选择忽略障碍物后距离最近的食物。

面对顺道的食物该怎么办

snake challenge中食物是会慢慢增加的，可能走到一半，你发现身边有个食物离得更近。这时候是否应优先去吃更近的？首先，我们说的更近都是忽略障碍物的情况下，虽然看上去近，但不一定真的近。其次原先的食物，虽然看上去更远，但不少路程已经探索过了，绕过新食物的路径是完全没有探索过的，更换目标也并不见得更好。路边的野花还是等下来采吧。

绝对不能吃的食物

有些食物刚好放在了陷阱里，吃完后无论如何都逃不出去。根据上面一条不吃野食的规定，你会绕着食物团团转，死不了也活不了。

我们加个步数的限制，如果食物距离5步以内，但你已经走了15步都没能将食物吃到，这时候还是换个目标吧。

寻路算法

寻路，就是如何才能最快的到达目的地。寻路算法中听的最多的就是A*算法。A*算法的核心思想是：

  1. 查看下一步能去的位置（去除障碍物等）
  2. 从下一位置中剔除已经走过的位置
  3. 算出所有：下一位置到起始位置的距离+下一位置到起始位置到目的地位置的具体
  4. 选择总距离最短的位置
  5. 将当前位置加入已经走过的位置列表
  6. 没看明白的自行google吧

对我们的贪吃蛇来说，可以将A*算法做到非常的简化。首先snake无法走斜线，无法后退，snake能去的位置只有三个，而且离当前位置的距离都为1。因此，我们只需要计算3个位置中那个位置离食物最近即可。在计算到食物的距离时，延续查找最近食物的方法，忽略障碍物。

除障碍物外，地图上还会有些危险物品，敌方的食物或是已经走路。

地方的食物，吃过后会变短，但还不至于挂掉。已经走过的路，虽然尽量不要走，但无路可走的时候，反倒也是个选择。

我们根据地图属性，给位置打分，然后选择得分最高的位置。

空（远离目标）: -9

空（靠近目标）：9

空（不变）：0

敌方食物：-20

已经走过的路: -40

墙：-999

蛇：-888

陷阱

地图上总会有些小陷阱，进去后发现是个死胡同，怎么都出不来。

做个递归，查看N步内是否有解，如果没解，那这步就别走了。

搭建自己的源代码托管服务

发表评论

现在要找个地方托管自己的开源项目是很容易了。老牌的有SF、顶着google旗号的googlecode、使用HG的bitbucket、以及我认为目前最好用的github。

不过如果你想自己搭建一个类似的服务，也是有些资源可以选择的。

  • gitorious （ROR开发，支持GIT）
    gitorious本身就是一个类似github的服务提供商，通过它提供的程序，你可以打架自己的本地服务。这个应用是用ROR写的，所以部署起来需要了解些ROR的相关知识。关于部署方式可参考 https://github.com/TGM/deploy-gitorious
  • gitube（Django开发，支持GIT） 
    国人使用django开发的一个git仓库管理工具。应用的完成度比较低， 而且作者似乎停止开发了。决定要用的话，得做好二次开发的准备。

 

注：DVS在权限控制方面存在天生的缺陷。Gitolite为git提供了权限方面的解决方案，这里有篇关于Gitolite的中文文档 http://www.ossxp.com/doc/git/gitolite.html。

LBForum已改造为Django的可重用APP

4条回复

LBForum分裂为两个项目

  • LBForum Django的可重用APP，包含有完整的模板。该app已加入pypi，可使用easy_install lbforum进行安装。
  • lbforum-site LBForum的演示站点。完整的Django Project演示LBForum如何集成登陆注册等模块。该项目可以快速的将LBForum跑起来。

最初写LBForum的时候为降低部署的难度，将LBForum作为完整的Django站点来进行开发。
实际应用过程中，不少人需要将论坛模块集成到已有系统中。
原有的方案在集成的时候有不少的问题。
而且整站的形式也不利于他人进行协作，若改动偏向站点的定制，会给代码合并的时候带来很大的问题。
在项目拆分后，在保证易部署特性的同时解决了第三方系统集成的问题。

LBForum演示站点

LBForum最新进展

6条回复

LBForum是我用python（django）开发的一个开源的论坛系统。

更多的信息可以参考我以前写的博客 发布一个Django的论坛系统LBForum（开源、带演示）。

最近LBForum也终于有了一位活跃用户，也非常感谢他给我提出了不少改进的意见。他们是一个游戏汉化组织，网址是 http://bbs.tuidao.org/ 。

LBForum现在主要具备的功能有：

  • 论坛分类，分版块
  • 发帖，回帖
  • BBCode支持
  • 使用AJAX实现附件上传、编辑
  • i18n支持，根据用户浏览器的语言自动显示对应的界面（目前支持英文和中文）。
  • 使用django admin提供论坛管理功能，实现对帖子的删除、修改、移动、设置置顶帖、关闭主题
  • 最新的功能更新参考 History

在我看来LBForum在功能方面已基本完善，对于LBForum以后的发展，目前还没有什么比较详细的计划。目前最缺的可能还是文档，只是一直没有什么动力去完善。功能方面也有些想做的，不过也是因为缺乏动力所以没太动手。

文档

  • 针对虚拟主机的部署文档以及相关脚本。python/ROR的web项目都存在部署麻烦的问题。对开发人员而言都够折腾了，普通用户基本上就可以直接放弃了。完善的部署文档，只少可以给用户们一个尝试的勇气。
  • 针对已有项目的集成文档。LBForum是以整站形式设计的。作为一个独立项目部署会比较容易，但和其他项目整合的时候和普通的app相比就要显得更麻烦些了。有了项目集成文档他们会觉得，原来要集成LBForum是这么简单的。
  • app说明，代码导航。方便二次开发的用户对代码的理解。

功能

  • 可视化的编辑器。最初规划的时候就有这个东西，不过因为一直没想明白这东西要在界面上怎么摆，所以一直迟迟没有动手。
  • 搜索功能。discuz等的搜索可选项太多，太过复杂。我可能会用Whoosh之类的东西做个全文搜索。只是如果论坛资源还不够丰富的话，搜索功能其实就是个摆设。
  • 积分系统。目前的大多论坛都会有自己的积分系统。我感觉将积分系统作为一个独立的app可能会比较好些。积分系统不一定要仅限于论坛，可以有多种的积分途径。参考了一下discuz的积分系统，发现者东西如果要真正做好还是挺费工夫的。
  • 站内消息。对现成的第三方app不是太满意，不过有些懒得自己写。

Android开发学习笔记（Android基础知识）

发表评论

发现实在是没有写笔记的习惯，每次都是写了一点后就没兴趣继续写下去了。随便摘抄点好了。

Activities and Tasks

task是一组相关的Activities，保存在一个堆栈中，给用户的感觉就是一个应用程序。简单的理解就是，每开一个新的Activities，就将Activities放到堆栈的最上面，按下back后就将当前Activities移除，激活堆栈上的下一个Activities。

Affinities and new tasks

其实我没太明白affinity的含义，在我看来似乎affinity有点类似taskId，标示它应该属于哪个task。

Launch modes

启动模式总共有四种

  • "standard" (the default mode)
  • "singleTop"
  • "singleTask"
  • "singleInstance"

Clearing the stack

默认情况下，如果用户长时间离开Task，系统会清理掉除ROOT Activity外的所有Activities。这个做法的依据是，如果用户太久没回来，用户肯定已经忘了自己最初做了啥，回来肯定是要做一些新事情。当然我们可以通过给activity设置一些属性来改变这个行为，比如alwaysRetainTaskState等。

Starting tasks

当需要一个activity作为整个应用程序的进入点时，我们给它一个intent filter,其中action为 "android.intent.action.MAIN"，category为"android.intent.category.LAUNCHER"。这种filter使得一个图标和一个标签显示在程序启动器中，使用户可以启动该task或者返回到该task。

Processes and Threads

同一个application都运行在同一个Processes里面。

为了保证Activity界面不阻塞，耗时工作应当放到Thread中。

Android有提供一个轻量级的RPC机制。

Activity lifecycle

Activity有三种基本状态：

  • active 当前活动窗口
  • paused 被其他窗口挡住部分
  • stopped  被完全挡住，在系统需要回收资源的时候会被kill

activity在进行状态切换的时候会触发相应的方法

  • void onCreate(Bundle savedInstanceState)
  • void onStart()
  • void onRestart()
  • void onResume()
  • void onPause()
  • void onStop()
  • void onDestroy()

Service lifecycle

一个service有以下两种用法

  • service启动后由service自己或其他人关闭。
  • 模块通过接口连接service（bindService() ），在调用unbindService()后关闭。

Broadcast receiver lifecycle

一个broadcast receiver只有一个回调方法：
void onReceive(Context curContext, Intent broadcastMsg)

broadcast receiver只有在执行onReceive的时候被认为是激活的。

当一个广播消息的响应非常耗时间时，需要新建一个新的线程来运行该操作。如果onReceive()创建了这个线程并返回，则整个进程，包括新创建的线程会被认为是非活动的（除非有其它的component为活动的），该线程有可能会被kill掉。解决方案是用onReceive()启动一个 service并让该service完成这个工作，那么系统直到这个进程仍然是活跃的。

END

到这里Android的基础知识也了解得差不多了，接着就该进军UI了。

Android的UI编程，主要注意的是：界面在XML中定义，为XML中的界面元素生成唯一的ID，并保存在自动生成的R.java中。程序中通过id查找相关界面元素，实现和界面的关联。除此之外的开发，和传统的java swing啥的没太多区别。

下面考虑写个简单的Android应用，一边学习，一遍实践。

Android开发学习笔记（Reloaded）

发表评论

深入浅出Android这书看到“解读程序流程”这部分的时候，我开始明白这确实是本烂书彻底的烂书。里面居然开始解释java程序的结构，啥是import之类的东西。一个人如果连java是啥东西都不做到应当也没必要看啥android开发。不过还在这书够薄，且凭借母语优势，我还是很快的把余下的内容给翻了一遍。感觉差不多可以照葫芦画瓢了，但对具体细节依旧是一头雾水。看来老老实实的看sdk自带的文档才是正道。

Android的开发者网站挂了，不过好在SDK里已经带了相关文档。

具体见：

/android-sdk-windows/docs/guide/topics/fundamentals.html

本着有中文尽量看中文的原则，先到网上找了找是否有Application Fundamentals的中文翻译。似乎已经有不少人做过了翻译，其中这篇翻译得比较完整http://docs.google.com/View?id=dcz49tvn_68f7rtrr9f

Application Components

Android程序比较特别，它不象大多程序一样有主入口。它是以“Application Components”为单位的，每个Components都是可以独立运行的。

系统中有四种Components：

  • Activities 主要用来处理用户界面（窗口）。
  • Services 后台运行组件，有点类似windows的后台服务。
  • Broadcast receivers 广播消息接收组件，比如电池没电，来电话啥的。
  • Content providers 用来处理各个application之间的公共数据存储，可以用来程序之间通信啥的。

Intent

content provider在接收到ContentResolver的请求时被激活，其他三种Components需要通过被称为intents的异步消息激活的。一个intent是一个Intent对象，它保存了消息的内容。

组件的关闭

Content providers和Broadcast receivers由android管理，通常不需要手动关闭。

The manifest file（AndroidManifest.xml）

应用程序配置文件，配置有该有用的组件信息，资源信息，以及权限信息。在android启动一个应用程序的component之前，它必须知道这个component的存在。因此，应用程序在manifest文件中声明了它的component。

Android开发学习笔记（程序目录结构及基本概念）

发表评论

选定《深入浅出Android》作为入门资料，同时还需要找个开源项目做参考以加深学习。虽然ADT本身有带不少例子，但我还想找个复杂点的例子。曾在java上看到javaeye android客户端开源的消息，于是就不费心去找其他的例子了http://code.google.com/p/javaeye-android-client/。

先创建一个新的Android主要目录如下

|~gen/ 系统自动生成的文件
| `~com/
|   `~haoluobo/
|     `-R.java
|~res/ 资源文件，图片以及界面描述等xml文档
| |+drawable-hdpi/
| |+drawable-ldpi/
| |+drawable-mdpi/
| |~layout/ 界面布局的描述文件
| | `-main.xml
| `~values/
|   `-strings.xml 字符串常量
|+src/ java代码

Android的界面虽然可以完全用java代码完成，但使用XML定义界面使界面和实现代码分开，更有利维护。且ADT提供了界面预览功能，可以直观的看到界面效果。

界面使用XML定义后，界面元素和java代码又要如何交互？所以就有了系统自动生成的R.java这个java类。ADT会在R.java里为XML里的界面元素创建对应的ID（int类型的常量）。根据元素类型的不同，常量保存在不同的子类中。这里说得有些不明白，直接上代码。

public final class R {
    public static final class attr {
    }
    public static final class drawable {
        public static final int icon=0x7f020000;
    }

…….

java代码里要获取对应的页面元素使用如下的方法

usernameField = (EditText)findViewById(R.id.username_field);

Android开发学习笔记（环境准备，学习资料收集）

发表评论

前言

iPhone推出后，移动终端的能量似乎被一下引爆，android的加入使这个市场更加繁华。智能设备的开发也一下子变得流行起来。

作为一个开发人员，还是很想了解尝试一下智能设备的应用开发。本想试试iPhone，无奈我没MacBook也没iPhone，只能退而求其次选了android。

环境准备

如果你只是学习android开发，那有台PC就够了，并不需要去真正买台android设备。

网上关于android的开发环境配置的文章已经够多了，这就不多废话。

具体参考：http://blog.csdn.net/ghd2000/archive/2010/04/19/5498673.aspx

这里要注意的几点：

  • 使用SDK Setup.exe安装的时候很可能会无法连接成功。选择Settings->Force https:// …http://。将连接类型由https改成http。
  • 如果修改过用户目录，会导致创建的AVD无法启动。需要将.android目录复制到C盘的用户目录，比如：C:\Users\vicalloy\.android
  • http://developer.android.com/ android的开发者网站悲剧的被墙了，需要自行翻墙

参考资料

开发环境准备好后，就要开始搜罗学习资料了。

具体的学习笔记

太晚了，改天补上……

发布一个Django的论坛系统LBForum（开源、带演示）

21条回复

简介

LBForum 用django开发的论坛系统，演示地址为：http://vik.haoluobo.com/lbforum/
项目的地址为：http://github.com/vicalloy/LBForum
界面部分抄的 FluxBB(一个开源的PHP论坛 http://fluxbb.org/ )。
虽然Django写的论坛也不少，不过还真没什么好用的。
大多Django论坛都是独立的app，而且不少还缺模板，想我这样有经验的Django用户要跑起来都觉得麻烦，其他普通用户就更别说了。
LBForum主要注重部署的方便性和易用性，功能方面目前还比较简单。
LBForum一开始就是以整站的形式提供，所以以LBForum做为基础项目进行二次开发是很容易的。
同时LBForum的开发尽量遵照Django可复用app原则，因此即使需要将LBForum做为独立的app集成到其他项目也并不会太难。

主要功能

目前功能还比较简单，而且还有些小问题有待修正。

  1. 论坛分类，分版块
  2. 发帖，回帖
  3. BBCode支持
  4. 置顶贴
  5. 使用django admin提供论坛管理功能

用开发服务器把LBForum跑起来

  1. 先把代码down下来。LBForum托管在github上，http://github.com/vicalloy/LBForum 。如果你没有安装git，你可以直接用界面右上方的download
    source功能下载代码。
  2. 运行\scripts\create_lbforum_env.py初始化lbforum的python虚拟环境。该脚本会自动创建一个python的虚拟环境并使用easy_install安装对应的依赖包，同时将一些依赖包解压到对应的目录中。
    注：django使用的是svn版本，所以机器上必须要安装有SVN，不然脚本会运行失败。如果因为由于svn的问题导致脚本运行失败，可以运行lbforum_env.bat进入lbforum环境，手动安装django的svn版本。
  3. 环境初始化好后，运行lbforum_env.bat进入lbforum环境
  4. 运行%mg% syncdb初始化数据库
  5. 运行%mg% runserver启动django开发服务器
  6. 进入admin，创建论坛分类和版块
  7. 进入版块发帖

LBForum的目录结构说明

|+lbforum_env/#lbforum运行的python虚拟环境，运行create_lbforum_env.py后自动创建
|+requirements/#lbforum用的第三方库和app，运行的时候会将该目录加到python路径
|~scripts/#工程相关脚本
| |-create_lbforum_env.py#初始化python虚拟环境，并自动安装easy_install/django依赖库
| |-helper.py#提供其他脚本所需的辅助函数
| `-lbforum_env.bat*#启动lbforum运行的虚拟环境及，并为lbforum的manage.py提供快捷方式%mg%，比如初始化数据库%mg%
syncdb
|~sites/#站点配置/模板/静态文件
| `~default/#默认站点
|   |+static/#静态资源文件，如css等
|   |+templates/#Django模板目录
|   |+templates_plus/#Django模板目录，用户将自己重写过的目标放到该目录
|   `-……
|~src/#django的app目录
| |+account/#account相关app。具体站点通常会对用户中心进行定制，所以该app在实际应用中很可能需要针对实际情况进行修改。
| |+djangohelper/#一些django的辅助函数等，
| |+lbforum/#lbforum的主app，论坛功能都在改app中
| |+lbregistration/#registration app的lbforum扩展，主要去掉邮件地址认证功能
| |+onlineuser/#显示在线用户的app（可复用的django app，可脱离lbforum单独使用）
| `+simpleavatar/#头像功能的app（可复用的django app，可脱离lbforum单独使用，依赖djangohelper）
|+tools/#工程用到的辅助工具，目前只有一个virtualenv的脚本

注：

  1. 由于计划在以后做i18n，所以目前只提供英文界面
  2. django的错误提示是显示在字段后面，fluxbb的错误全部都显示在表单前面。由于模板没有调好，所以目前按照fluxbb的方式显示错误，所以错误显示有些不太正常。
  3. bbcode的输入框本想做成自适应大小的，不过也调得有些问题，所以现在输入框的大小固定。
  4. 文档… ，感觉好难写-_-，目前文档不全（项目中没有带任何的文档），日后补上。
  5. 应用程序的目录结构主要查看pinax
  6. simpleavatar模块部分代码来自django-avatar
  7. 依赖包除用easy_install在线安装的外，尽量使用zip包的方式附带在项目中，减少安装依赖包的困难。
  8. 远程部署脚本计划使用fabric，但fabric本身安装比较麻烦，所暂未处理。
  9. 项目最早放在googlecode，不过感觉github的功能更强些，所以移了过去。

SourceForge使用Python、TurboGears、MongoDB……来重构网站

1条回复

pycon2010上关于SF网站重构的演讲，里面介绍了SF重构的技术选型及原因。在我看来SF用的东西还真的很GEEK。
主要用到的技术有Python、TurboGears2、MongoDB、Jinja*、RabbitMQ，服务器用的是LigHTTPd和Nginx。

  • TurboGears2（为什么不的Django？）
    pdf中也有谈到此前也用到过django，而且有很不错的体验，但对SF的改造来说TG更为合适。SF有着上10年的历史，要完全抛弃原有的东西自然不现实，此次的网站重构并不是完全的重写。TG可以很容易的剥离掉不需要用到的东西，同时TG可以很好的同其他WSGI中间件配合工作。
  • MongoDB
    MongoDB是一个非关系的分布式数据库(NoSQL数据库)，最大的优势快。由于这东西足够快，所以连web2.0网站常用的memcached也省掉了。(注：NoSQL数据库介绍可以参考 NoSQL数据库探讨之一 － 为什么要用非关系数据库)
  • Jinja*
    Django的模板很棒，但速度不怎么快，而且完全不支持任何嵌入式代码。Jinja和Django的模板长得非常的象，而且解决了上面的两个问题。（注：文档里说前台用的是PHP，所以不清楚是否有部分用到Jinja）
  • RabbitMQ
    用Erlang写的中间件，进行前后台的消息通信。SF的前台界面呈现，依旧使用的PHP，前后台通信用的就是这东西。