john_he 发表于 2007-11-30 17:33:34

懒人求个算法……

事情是这样的……
偶想实现一个游戏引擎用的文件管理系统,把磁盘文件和不同种类的压缩包封装成一个统一的接口。现在正愁怎么快速查找不同包里的文件(使用*,?通配符那种)。

之前是打算初始化时先扫一遍全部文件,以(文件名—(压缩包,偏移))的形式保存信息在STL的map里面快速搜索的,现在想加入通配符查找,除了遍历map外还有什么方法??

rednaxela 发表于 2007-11-30 17:53:35

<- 也懒得手写匹配的人
通配符的匹配似乎可以用boost::regex? 但遍历一个装有文件索引的容器恐怕是无法避免的,毕竟“通配”是要完整搜索才能确定的啊。

要不要看看FlipCode上的一个虚拟文件系统是怎么做的?
http://www.flipcode.com/articles/article_vfs01.shtml
我还没来得及读这系列的文章,不知道里面有没有提到通配符这种场景的解决

shawind 发表于 2007-11-30 19:06:13

有个问题,为什么不事先作成文件名+偏移量的列表并排序好以供查找,而是在游戏初始化的时候再扫描?
如果小文件多了,这游戏的初始化会不会等死人

lw 发表于 2007-11-30 21:08:18

私下交流一下罢囧大(玩笑了XD)。。。

以前做过一个很简单的文件打包的,不过就是如SHAWIND大所说的,可能更加简单……
如果在就Q偶好啦^^

lw 发表于 2007-11-30 21:11:12

其实一般打包都用的D版的MOLEBOX,反正只是玩玩的哈哈^^
懒啊懒,其实有个打包的确实不错…………

john_he 发表于 2007-11-30 23:24:55

通配符的匹配算法是有了,打算重写GNU的那个,有点对不起GPL就是……
现在问题是如何进行尽量少的比较,而不是遍历整个map,毕竟比较1000多次消耗太大……

有个问题,为什么不事先作成文件名+偏移量的列表并排序好以供查找,而是在游戏初始化的时候再扫描?
如果小文件多了,这游戏的初始化会不会等死人

文件名+偏移是会保存在文件头里的,但初始化时会挑一部分信息保存到内存里,毕竟频繁读文件头也不太好……至于排序保存,的确是个好提议……

现在貌似很多引擎也是初始化(程序刚启动)的时候扫描文件列表的,延迟不是太明显,最多就两三秒,但以后游戏循环里就节省了很多时间。

rednaxela 发表于 2007-11-30 23:54:13

排序要看情况。John大决定用std::map的话排序了也不顶事——它本身就是带排序性质的红黑树。
确实有很多引擎会对不在archive内的文件预先建立文件索引(因为archive本身就应该有索引所以不用对里面的文件另外做索引),例如Circus用的引擎就会单独建立一个“编译”过的索引。但是那种一般是配合一个整合开发环境来使用的;人手建立索引很烦琐(主要是来回调试可能会忘记),所以不像是什么好主意。

如果是这样的通配:"abc*",那即使不用map而是用一个线性容器,预先排好序的话确实是可以在检索到例如说abd*的时候就停止遍历。但如果通配项是:"*xyz",先前的排序就不起作用了。无法两全的,还是整个遍历吧。其实并不会消耗多少时间的,比起I/O来说……

FlipCode的那个例子在演示如何统一实际的文件系统与archive的文件读写方面应该做得还不错,吧……

rednaxela 发表于 2007-12-1 00:07:42

引用第5楼john_he于2007-11-30 23:24发表的:
通配符的匹配算法是有了,打算重写GNU的那个,有点对不起GPL就是……
是指GNU Regex么?还是别的?

john_he 发表于 2007-12-1 00:17:19

的确有理……

我有个想法是,因为通配一般不允许目录使用通配符,即不允许/foo/*/bar.txt之类的方式,所以是不是可以分成路径和文件名两部分做map,使用路径的map检索对应目录下文件名的map,这样匹配的时候就可以少比较很多次。代价也许就是空间消耗大和结构变得复杂……

考虑到通配在游戏里用到的机会应该不会太多,我想还是遍历算了,实在是懒……

FlipCode的例子有空看看……

确实有很多引擎会对不在archive内的文件预先建立文件索引(因为archive本身就应该有索引所以不用对里面的文件另外做索引)
我就是想对Archive里的文件索引……因为可能要使用好几个Archive,要快速查找在哪个Archive里的哪个位置……
另外,实际文件系统是抽象为一个Archive的,像Ogre那样……

john_he 发表于 2007-12-1 00:25:18

引用第7楼rednaxela于2007-12-01 00:07发表的:

是指GNU Regex么?还是别的?

fnmatch.c
很久以前找回来的,忘了哪里的了。刚看了看又好像不是GPL的,是BSD的,而且到底是不是GNU也不是很记得了……老了……
不过因为要的是wchar版的,所以肯定要改就是……
页: [1] 2
查看完整版本: 懒人求个算法……