罗马，my oh my, 罗马！

罗马是如此地辉煌，如此地繁荣。历史在罗马留下了无数的痕迹。每一个转角，每一个屋檐，每一块砖都流露着昔日的辉煌。无数个电影的场景，无数个小说的情节，总会说到这个城市。不知道多少年以前就发誓有一天要来到这里，今天，终于如愿以偿。

当然，每次旅行总会遇到一些杯具，比如我们到罗马的当天是公交车大罢工。所以一行人决定开车从旅馆到第一站——Galleria Borghese

诶？我拍的比wiki上面的好？见鬼了。。。

在这里不能不提，在罗马飙车简直是我这辈子最刺激的经验。明明是3条线，可以开5辆车。在罗马的交通面前，北京二环的taxi司机也会手潮。行人完全不看红绿灯，左转全靠感觉。最扯的是一条路拐4个弯名字还一样。好不容易才到达目的地。

其实挺悬的，我们是在闭馆前5分钟冲进去的。上面的照片是出来以后才拍的。楼梯上已经没有队伍了。

艺术馆是不能拍照的，这是一个很大的遗憾。没关系， 让我找到网上的图片来给大家分享

来到罗马的第一个震撼，我看到了Antonio Canova的作品Venus Victrix

老妈很多年前去过罗马，曾经购买到一本罗马的旅游地图。书里面有很多介绍，看到这个作品的照片的时候我只能用“震撼”来形容。一块白色的大理石可以被人雕琢成这个样子，无论是床垫的皱褶，人体的肌肤，还有陷入垫子的一个个细节，以及衣服垂下的感觉。真的理解什么是活生生的雕塑。

但是走到近处，你会发现更多的细节。垫子是镶了边的，有很多小小的细节浮现在作品的每一个角落。

看到背面你会注意到人体的每一块肌肉，腰部因为弯曲受力的不同。

我看到的第一感受就是泪流满面。真的是泪流满面，因为太震撼了，太真实了，名家的作品，就这样子在你的面前。这是我来到罗马几天一直都在重复的感觉。

后面展厅还有两件更令人崩溃的作品，贝尼尼的Rape of Proserpina和Apollo and Daphne。

看到雕塑的细节，才理解什么是巧夺天工。

下图是Rape of Proserpina。

比如Rape of Proserpina侧面Pluto抱住春之女神的腿的细节，手指陷入挣扎的肌肉的样子。

下图是贝尼尼的Apollo and Daphne. Daphone是罗马神话里面的一个精灵，阿波罗则是预言之神。阿波罗疯狂地爱上了Daphone，Daphone为了守住自己的童贞，于是向众神求助，她的父亲就把她变成了一棵月桂树，于是，月桂树就成了阿波罗的圣树。

雕塑里扑捉了Daphone变成树的一瞬间，完美地把人的动感，伤痛的表情和树木结合成一体，凝固住了这个瞬间。

后来发现在罗马，这样的雕塑简直随处都是，多到让我崩溃。每一个转角都是名家之作，哪怕只是一个小小的阳台。最扯的是，阿波罗脚上的鞋的样式，到现在店里还在卖。。。。。

离开Galleria Borghese，奔向注明的西班牙广场。

当然，现实和想象还是有差距

想象图：

别人拍的：

现实中我拍到的。。。。

从山上拍下去看到的西班牙广场。

人真多啊，呵呵。天气热。据说罗马的水很干净，喷泉的水是可以喝的。因为没有带什么药，所以就放弃尝试了。呵呵。

随后来到Trevi Fountain。这就是著名的罗马许愿泉。据说扔下钱币的人，可以重回罗马。我也许了个愿，希望可以如愿以偿吧。

说真的，长这么大没见过这样子造喷泉的。整整4层楼高啊！

吃过晚饭以后返回这里，坐在喷泉前面，看熙攘的游人。水在奔流，你可以感觉到水里的战马简直就要飞跃出来。不坐在面前，真的无法体会这里的魅力。

罗马，my oh my, 罗马！真的希望可以有一天重回这里。

话说。。。。罗马M记卖的salad里面有鱼和虾，配的是意大利香醋和橄榄油。绝对是入乡随俗。让我想到了著名的M记老北京鸡肉卷，还有珍宝三角etc…..扯远了。

回住处前，入手了著名的Roma pass

大家以后路过，一定要买哦，可一订任意两张门票，很多地方不用排队买票（比如斗兽场），还可以免费做公交两天。嗷嗷好啊！

罗马的第一页就到这里。

//P.S.开会去的路更恐怖。。。。因为是晚上，路还不熟，我发誓以后一定乖乖坐公交车。。。

很久没有更新了，前一段时间忙得的快要吐血了。天天被火烧屁股。过去一周终于喘了口气，处理了一堆照片，终于可以继续写啦！

那么，我们继续。

意大利人菊花常紧？

对我来说威尼斯是一座神秘的城市。建设在亚得里亚海的海湾里面，这里有着欧洲的浪漫，建筑，历史，艺术。街道边有些老房子的大门已经半浸在水里，虽然油漆的颜色还是依然鲜艳。

话说住的地方。。。。

怎么样，是不是看起来嗷嗷牛B？其实是在工业区的中间，但是好在门口有车可以搭，很方便，也很干净的一个酒店。住的很舒服。

第二天一早来到威尼斯，意大利人很是慵懒，早上9点才开始准备。在岛上随处的人的打扮都很亮眼。这是一个随便抓拍到的姑娘，在去岛上小店开工的路上，真的很美。

威尼斯是个水城，并不只是一个旅游的地方。这里有着常驻的居民。 所以自然也有商店。比如蔬菜和水果都是船运而来，很是神奇。可惜店主不让我拍照，只能躲得远远地拍一张。

岛上也不乏小酒馆，里面的摆设很是精致。

威尼斯的美丽，带有一丝恬静的热情，大概可以这样形容吧。

威尼斯本质上是3个岛，由一条大运河分开。经过不知道多少小巷和桥，我们来到安康圣母圣殿。

不要觉得这个教堂外面看起来很壮观，看看下面这张网上找来的图，你就会注意到这个教堂简直就是在水上。当你站在他的脚下，你真的会很受震撼。

One more look…

当然，既然第一次来到威尼斯，肯定少不了著名的刚朵拉。我们的舵手很风趣，还是个大帅哥。

刚朵拉总是穿梭在这样的箱子里，可以看到很多平时完全接触不到的东西。威尼斯岛上还有几个很著名的剧院。晚上的时候会有歌剧的演出。最强的是有几个剧院只有通过船只可以到达正门。无论是演员还是观众都只能乘船到达。

说到意大利人，总是忘不了这个手势：

一直找不到确定的意思，我就问了我们的舵手，到底是什么意思。

舵手想了一会儿告诉我两个故事：

一、你到了一个地方，人山人海，你觉得很有鸭梨

二、你受惊了

你会菊花一紧，就是这样了。。。。

不知道为什么表示一个东西很好吃的时候也会菊花一紧。。。。。意大利人还真是菊花常紧。。。。

岛上的教堂多到了令人发指的境界。每一座都美得一塌糊涂。真想住在这里感受每座建筑上面每个细节。太美了。。

随着曲折的小径，回到了昨天傍晚经过的圣马可广场。大家也许还记得昨日落日余晖中的St Mark’s Basilica，就在下面图片的远处。

St Mark’s Basilica里面是不可以拍照的，因为全部的屋顶和地面都是真的金做的马赛克。大约是下图的样子（网上找来的）

圣马可广场的鸽子真的很多。老爸老妈味得很开心。照片就省略啦。

离开了圣马可广场的我们踏上了离开威尼斯的路。有一天我一定要回到这个美丽的地方。这个地方真的太神奇了。

一行人驱车赶往中继站，罗密欧与朱丽叶的故乡——Verona.

View Larger Map

路上遭遇了欧洲一行最夸张的一次堵车。堵了4个半小时。。。。那一段路才一小时而已。欧洲的堵车和北美不是一个概念。首先是路边没有紧急通道，第二是车的密度实在是高，第三是堵车以后是完全停止不动。

来到Verona已经是傍晚。吃过晚餐的一行人累得不行，在老妈坚持下，还是冲进城里逛了一圈。

一人份的Pizza+酒，尺寸太夸张。

小城很美，很安静。晚上9点半一堆人坐在街边吃Pizza。

小斗兽场进不去，因为夏天是opera season。里面正在准备布景。可以听到排练的声音。下一出要演的是图兰朵。

不确定的同学可以去听《今夜无人入睡》，你一定听过。可惜帕瓦罗蒂已经不在世了，真的是可惜，可惜。。。。

http://www.youtube.com/watch?v=VATmgtmR5o4

晚安，威尼斯，晚安，Verona，晚安，意大利。

今天就到这里。过两天继续。

预告一下，下一站——罗马

现在的我们是如此地浮躁，匆忙地起床，匆忙地上路，匆忙地晚餐，匆忙地睡觉。日复一日的生活没有给我们留下喘息的机会，回首看看自己走过的路。

我的生活就像在下坡上的滑板，越滑越快，路旁的风景已经渐渐模糊，也不知道路的尽头有什么在等待着我。

或许日子就是这样，或许生活就是这样。

意大利人腿真长，莫扎特这个小短腿当年也是个杯具

从萨尔斯堡出发前往Innsbruck。早餐依然是嗷嗷牛B。

|靠谱的瓷器

|自己装盘的食物

达到后停在Maria Theresien-Strasse的尽头，开始步行。我觉得这个城市是很典型的奥地利小城。这个城市曾经两次举办冬季奥运会，到现在还能看到远处雪山上面的滑道。

|城门

在街道的尽头是Godenes Dachl（金顶屋）。其实就是一个金顶的阳台。。。原来是公爵的府邸。

|金顶屋，其实就是个金顶的阳台。。。。据说是真金

一不小心错过了Swarovski的总部，因为时间关系没有多看。

收拾好行头就开始一路奔向意大利。这是第一天正儿八经地开车，欧洲人开车很野蛮，大货车换线不会提前给你任何信号。有一次险些被挤到护栏上面去。

穿越阿尔卑斯山脉，来到了意大利北部。一路上风景如画。给我的感觉是欧洲人喜欢在山尖上盖房子。几乎每个像样的山头都有个城堡。路上远处还看到几个很壮观的城堡，可惜没有机会下去。我回到Seattle以后一定要把沿路的城堡都找出来研究研究。

傍晚时刻终于达到了威尼斯。意大利的路各种纠结，到处都是round-about，各种转圈圈，搞得我们头晕脑胀。我上周更新的欧洲地图还有各种看不到的新路，我们要经过的一条重要通路居然封掉了，绕过至少20公里才达到住处。

扔下东西，直奔威尼斯。这时已经将近日落。

众所周知，威尼斯是个水城。本质上是亚得里亚海湾里面的一个小岛。本来是没有通路的。后来因为游客的不断增加，才有了高速公路和铁路。

以前总听说这里的水很臭，本来以为要捏着鼻子逛街的。后来发现远没有想象的糟糕。因为海水的不断侵蚀，城市的建筑都很老旧，但是街道依然赶紧，小城里面人们的生活也是井井有条。

|威尼斯，下午

|水城，小街

|街头的人们

岛上的路非常难走，一天下来总结的经验是，不看到指示牌不转弯。在小巷里绕了20多分钟以后终于到达大运河的边上。沿着运河来到了Rialto桥。在路上已经走过了无数的小桥，到这里才知道什么叫壮观。

桥有三进，全部是大理石修成。这也是大运河上面最老的桥。

|威尼斯最老的桥，也是最高点处最壮观的桥

岛上的Pizaa非常靠谱，这也是我到意大利以后第一次吃Pizza。味道真的不错。4欧元一片，说得过去。

|威尼斯的Pizza

过桥来到岛的另外一边，圣马可广场就在这里。广场比平时照片里看到的大了很多。日落时分的色彩给本来就神秘的广场蒙上了一层美丽的色彩。在这里拍到了St Mark’s Basilica的外景。明天准备再访。

|教堂一角，一抹余晖

经由Accademia桥来到南边的岛上，这个岛同时也是Santa Maria della Salute的所在地，可惜时间已晚，不想在威尼斯走夜路的我们沿着小巷子向车站前进。

|日落威尼斯，摄于Accademia桥上

岛上的巷子很窄， 真的是寸土寸金。威尼斯曾经是世界上玻璃的唯一产地，同时也出产威尼斯面具。街边的小店铺玲珑满目，几乎没有重样的。

|街边小店

|美丽的街道

|画一样的水道

|傍晚一景，岛上的住民已经很少

回到旅馆后第一件事情当然是就地留名。结果在马桶上发现了一个悲剧，意大利人腿真长。我这个181.5（注意，有.5）的个子坐在上面和座吧台椅没什么区别，脚不着地发起功来总有些内力不足。想到莫扎特也曾到意大利演出，他这个小短腿当年也是个杯具。

收拾行头，第二天准备再入威尼斯！

|晚安，威尼斯，明天再见

HB就是青岛啤酒的祖师母

欧洲的网络真不发达，满哪儿找不到wifi，搞得我欲哭无泪。于是由每日连载改成哪天有wifi就哪天连载。

到达慕尼黑的时候已经是晚上大概5点多了。扔下东西以后就奔向市中心的Marienplatz。

慕尼黑的纬度很高，夏日这个时候天黑得很晚。走在步行街上面的人很多。即便是周一的晚上，每个小酒馆屋外的桌前都坐满了客人。

欧洲人的生活很悠闲，每个人的面前都摆着大大小小的啤酒杯。走在街上，许多住家的窗口都悬着花盆，古老的雕花窗口被五颜六色的花朵陪衬着，无不给这个历史悠久的城市添加的许多的生机。

步行街上四处都是贩卖水果的摊子，不知道为啥大家都在卖白色的芦笋，估计是正好到了季节。

不知不觉之中来到了（两个大绿顶）教堂。教堂的塔顶非常有特色，感觉造型很受东正教教堂的影响，完全不像Marienplatz里面教堂的哥特式屋顶。在德国这样一个宗教单一的国家里，一个城市里面会有两个迥然不同风格的教堂也算是一种奇观了。

从教堂继续前行来到Marienplatz。这里的建筑是很夸张的哥特式风格，让我想起了很多游戏的场景（比如Assassin Creed）。 后面会更详细地介绍。我们一行人沿着广场边的后街来到了HB的总部。

HB(Hofbraeuhaus)是德国最畅销的啤酒品牌。大厅里坐满了世界各地（特别是中国）来的粉丝。一个很胖的中国大叔卖力地指挥着演奏的乐队，看来这啤酒的确不错。。。。

|HB总部

大厅的一角有几排上着锁的柜子，里面存放着的是常客们专用的酒杯。

|上了锁的酒杯柜子

吃了店里推荐的烤猪肉，配菜是土豆丸子。味道非常让我失望。唯一感动的是啤酒。在青岛长大的我，很喜欢青岛啤酒的味道。HB就是青岛啤酒的祖师母。麦子、啤酒花、发酵的味道都比青啤要浓很多，让你从骨子里明白什么叫啤酒。

（当然，喜欢浓一些啤酒的同学们请点黑啤）

|青岛啤酒的祖师母

|烤猪腿和。。。。？？0_o

酒足饭饱以后，回到旅馆倒头就睡，睁眼的时候已经是早上8点钟了。

下楼吃饭，早餐还是依然精彩。这天还多了血肠和（软奶酪）可选。但是我也发现了，德国人不喜欢吃冰的东西。所有的橘汁、牛奶等等，只能说是冷，和水龙头的温度差不多。

|慕尼黑的早餐

拿到车子以后，一行人再次踏上征程，奔向这天的第一站——Schlosspark Nymphenburg。虽然不能说让我大失所望，但是本质上也就只能到此一游。这里是路德维希国王的夏宫，比起承德避暑山庄来说，这个行宫真是简陋到了一定程度。

Theatinerkirche ，是个很有特色的地方。虽然并没有什么让人惊艳的感觉，但是街边的狮子雕塑，拱门上精细的浮雕和街边悠闲的人们，无一个不流露着欧洲的气息。

12点钟赶回了Marienplatz，站在钟楼前看着跳舞的人偶，想到这是几百年前的作品。从头看到尾，才发现这里面讲述了一个故事。这里的人民经受着外来的入侵，这时候一个英雄站了出来，带领着骑兵打败了敌人，快乐的人们跳着传统的方块舞庆祝胜利。

驱车来到了萨尔斯堡(Salzburg，直译是盐城堡的意思)，这里是音乐大师莫扎特的出生地，指挥大师卡拉扬的故乡和电影音乐之声的拍摄地。

|萨尔斯堡，全景

|萨尔斯堡，全景，上上

萨尔斯堡是个山坳里面的小城。除了满大街挤满了的游人，一切都那么地恬静。

|小城街道

登到山上来到了萨尔斯堡要塞，这个是萨尔斯堡的象征。多年前曾经是一个重要的要塞，占据城里最高点的城堡。整个外墙都刷成了白色，没有辜负盐城堡的大名。

从城堡下山的半路上经过了岩石教堂，这是一个很不起眼的教堂，完全是靠岩壁里的隧道挖掘出来的。里面的空间也很小。

|岩石教堂半路上

下到山脚，走到了著名的Getreidegasse。街边仅是各式各样的小店。当然，看看下面的图片还会发现让你崩溃的麦当劳。

萨尔斯堡城外 遭遇了来德以后的最大悲剧。请看下图：

厕所里，左边门上写着Herren，右边门上写着Daman。我琢磨，Her=她，ren=人，那就是女人咯，Daman，这个就更简单了，Hip-hop里面不就是The man的意思嘛。直接推门进去，一个大妈一脸崩溃地看着我。我泪流满面地退了出来。。。。。

收拾干净以后，继续前进。进入了Salzburg Cathedral。这座教堂门口写着三次建设的年份。里面墙上的浮雕非常让人赞叹。悬空的水果栩栩如生，天使脸上的表情，眼睛的细节一丝不苟。宗教的力量真是伟大。

|精细无比的浮雕

教堂侧面是Residenzplatz，里面有一座著名的喷泉（见下图），其实还蛮失望的。。。。

回到住处吃晚餐。三个人分别要了猪扒，牛排和煎鱼。附送了前菜和炸土豆。

|迷迭香炸土豆

|鱼

这里真的值得细说一下，炸土豆是和迷迭香一起炸的。送来的前菜也非常出彩，嫩煎牛排陪兔肉做的冻肠，配上意大利香醋和冬青叶橄榄油。一切都恰到好处。主菜里面的煎鱼做得非常有追准，食材也是非常新鲜的鱼肉。这里不多介绍，以后有机会复制给大家。其他两样也都是上乘水准。只可惜价格有点贵（一个人大约26美刀）就在这样快乐的一餐里面结束了第二天的旅程。

终于有网了，感动！

小时候总是喜欢看飞机起飞的样子，看着地上的房子慢慢变小，汽车渐渐变慢。于是总是专门要窗口的位置。

后来长大了发现两点：

1.窗口的景色不再那么吸引我

2.人老了，要常上厕所，懒得麻烦旁边的人

昨天领取登机牌的时候，柜台姑娘问我要窗口还是过道的座位，我想也没想就要了过道的座位。后来有点后悔，于是又补了一句，要窗口那边的。

飞机是波音767，座位是 2 4 2。也就是说，窗口边只有两个人坐^^。

但是最后还是崩溃了。同座的德国姑娘平均两小时起来一次散步。还没看到景色。我就这样变成了茶几。

—————

在这里不得不先抱怨一下飞机。首先是食物，让我这个很不挑剔的家伙忍无可忍。幸好自己带了点儿零食充饥。其次是干燥。下飞机的时候感觉自己像撒哈拉来得难民，找到水咣咣猛喝。

（哇，难道德国的电不一样？笔记本充得非常快啊。）

飞机落在法兰克福。飞越城市上空的时候瞟（注意，不是看）到外面的景色。河蜿蜒地流过城市中心，深绿色的森林里点缀着红色瓦顶的房子。和16年前的样子完全一样。多少让我想起了一些曾是德国殖民地的青岛。看着看着，飞机穿越了云层，汽车渐渐变快，房子慢慢变大。。。。。

这次旅行的一大目标是斯图加特的奔驰汽车博物馆。很崩溃的是德国的大部分博物馆在周一都不开门。

飞机13:20到达，出关13:40，我们一路直奔火车售票处。一个热情的大叔在一番介绍以后推荐了任意3天有效的特种票给我们。外国游客凭护照可买。

|售票处

|车票

14:47坐上了ICE高速列车，奔斯图加特而去。

|高速列车

ICE最高时速300多公里，车子里安静到让人发指的境界。本质上比我家里的卧室安静。我当时还仍有一些时差，直接就昏死过去了。

—————-

奔驰博物馆的外观很有特色，让我想到了一个扭曲的水煮蛋。

里面陈列着 ——————————汽车

|著名的300SL

好，不要觉得很冷。里面陈列的的确是汽车，从世界上第一辆汽车到2010年最新的SLK系列概念车。下面是一些选出来的经典：

—————-

住在市中心的一个小旅馆，其貌不扬，进去以后才知道什么是欧陆风情。浴室大概有我现在的浴室1/4个大。更加强大的是旅馆的电梯，上面标注可以乘坐5人。我们一家三口勉强可以挤进去。突然又一次觉得减肥的必要。

当晚在一家小餐馆搓了一顿。好歹算是把飞机上饿着的份儿吃回来了。两杯啤酒下肚以后，感觉欧洲之旅就这样正式拉开帷幕了。

|第一天的晚餐，绝对传统。 啤酒相当不错！

第二天一早就下楼吃早饭。又一次感慨欧洲人生活真tmd的好。没什么好说的，直接看图吧。

|餐具+杯具

|家母表示：这只是一般水准

回到了父母大学时的宿舍，十几年过去，楼里连味道都没有变，一开门，回忆扑面而来。

日子是过得如此匆匆。我们都不曾驻足回忆。花儿开了又谢，谢了又开。青春就这样，一去不复返了。

|斯图加特火车站里面的小火车，小时候就爱玩

回到斯图加特市中心，坐下来吃甜点。注意！！冰激凌是用玻璃杯装的！！怪不得欧洲人各种鄙视美国人。

一口吃下去，只能喊，我靠！4种梅子都是用朗姆酒煮过的，上面的炸面包球也浸过了白兰地，配上下面四种口味的冰激凌，一口下去吃得我内牛满面。这，揍四省活。

|特别推荐——梅子冰激凌

据说斯图加特是个很没有文化的城市，可是我怎么觉得每一步都是景色呢。。。

现在是下午4:06。我正坐在ICE上面奔向第三站，慕尼黑。

More pictures here: http://www.flickr.com/photos/2bethere/sets/72157624104351085/

2009Fireworks_02, originally uploaded by tsxy.

刚才有一个好搞笑的警察开过去了。。。。

This is a test post from , a fancy photo sharing thing.

还有一个半小时就要登上飞往法兰克福的飞机。在法兰克福当地周日13:20着落。

此刻我的心情很平静，西雅图的机场还是一样的熙熙攘攘。好在有免费的wifi可以用，使得这一个半小时的等待不那么漫长。

已经很久没有这样出游了。还记得小时候非常喜欢坐飞机。因为离开舱门的那一刻眼前总是一个不一样的城市。连空气的味道都不再一样，我很喜欢这样的日子。

工作以后变得经常飞来飞去。各地的朋友，各地的事情，还有远在大陆另一个角落的家。渐渐地背过了每一个机场的代号，记得了每一个机场转机的路线，熟练地通过安检。飞过的里程越来越远，经历的故事也越来越多。还记得在扭腰的JFK卡了20个小时，在芝加哥的ORD过夜，在亚特兰大的ATL座轻轨转圈圈。。。。。

后来看到George Clooney演的Up in the Air才懂得，我害怕寂寞，喜欢孤单。

回头看了一眼窗外，天气很好，是难得一见适合远行的日子。未来10天欧洲的天气也很好。非常期待未来这两周的trip。飞机离起飞不远了，收拾收拾去登机了~~

欧洲见。

I was suppose to post an article on Code Project about this, but there is a new project that I need to work on ASAP, the article will have to wait.

This post will serve as a quick intro to the path finding world. Everything is implemented in C#. If you want source code, post in comments and i’ll get back to you.

This article is written by TSXY [at] 12thocean.com. Website: http://blog.12thocean.com
You are welcome to repost or use any part of the article for your own post. Source code are available upon request. Please send me a link if you post this anywhere.

First one is DFS or depth first search. As you can see, it’s not very smart. Due to the fact it’s looking down the road accoding to a predetermined path. In this case, counter clock wise.

Well, this obviously is not a good solution, people then started think more efficient way to find a path. In this case, a 3 line change to our non-recursive DFS made it into BFS or breath first search. The idea is simple, look at all your neighbors before moving on.

Here is the result, impressive, but not efficient enough. Why? just look at the memory comsumption. The little blue squares means that block was part of the search. Not very efficient..

Then there is the ultimate algorithm for correctness. (Note, not efficient, but correct) Dijkstra Algorithm.

This is designed to evaluate all possible routes and find the minimun path. Kinda like dynamic programming, where you keep looking for ALL possible solutions and update the grid with lowest solution.

The result is impressive, since it’s the most efficient path. The cost? LOL. I don’t even want to think about it.

Well, those are obviously not great solutions, what people came up is a combination of DFS and Dijkstra Algorithm. The idea is simple – Instead of looking at all possible routes, try the one closest to the destination first. And the result? Can I say WOW! Look, no square is wasted during the path finding.

This is super smart in terms of path finding. It’ll find a close to optimal result all the time. But as you can see, it’s not THE most efficient path. Why? Because there is a function, let’s call it G(x). G(x) is the estimated cost from cell x to destination. In this implementation, G(x) is the direct distance between x and destination. The cell with lowst G(x) will be evaluated first. This makes sense since this cell will “likely” be closer to the destination.

However, it might not be correct due to blocks on the road etc.

Then here is the ultimate algorithm. I call it A* Plus. Since it’s just a little addition to A*. It finds the optimal path, while uses far less memory than Dijkstra.

How? It’s all about how G(x) is designed. In this case, G(x) is direct distance + Obsticals on the direct path.

It’s very tricky to count obsticals along the path as you may notice. I actually implemented  Bresenham’s line algorithm to calculate the cost.  And the result:

Now let me mark this to be the end of this project. It’s unlikely for me to do the actual post to code project at this point. But who knows!