懒人求个算法……

john_he

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

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

rednaxela

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

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

shawind

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

lw

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

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

lw

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

john_he

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

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

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

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

rednaxela

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

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

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

rednaxela

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

是指GNU Regex么？还是别的？

john_he

的确有理……

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

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

FlipCode的例子有空看看……

确实有很多引擎会对不在archive内的文件预先建立文件索引（因为archive本身就应该有索引所以不用对里面的文件另外做索引）

我就是想对Archive里的文件索引……因为可能要使用好几个Archive，要快速查找在哪个Archive里的哪个位置……
另外，实际文件系统是抽象为一个Archive的，像Ogre那样……

john_he

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

是指GNU Regex么？还是别的？

fnmatch.c
很久以前找回来的，忘了哪里的了。刚看了看又好像不是GPL的，是BSD的，而且到底是不是GNU也不是很记得了……老了……
不过因为要的是wchar版的，所以肯定要改就是……